home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / logic / 2115 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  1.7 KB
  1. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!uwm.edu!ogicse!das-news.harvard.edu!husc-news.harvard.edu!husc10.harvard.edu!zeleny
  2. From: zeleny@husc10.harvard.edu (Michael Zeleny)
  3. Newsgroups: sci.logic
  4. Subject: Re: Logic and Mathematicians
  5. Message-ID: <1992Nov19.230948.17624@husc3.harvard.edu>
  6. Date: 20 Nov 92 04:09:47 GMT
  7. Article-I.D.: husc3.1992Nov19.230948.17624
  8. References: <1992Nov15.191744.17481@husc3.harvard.edu> <1992Nov16.222220.7956@dorsai.com> <56452@dime.cs.umass.edu>
  9. Organization: The Phallogocentric Cabal
  10. Lines: 29
  11. Nntp-Posting-Host: husc10.harvard.edu
  12.  
  13. In article <56452@dime.cs.umass.edu> 
  14. yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
  15.  
  16. >In article <1992Nov16.222220.7956@dorsai.com> 
  17. >mutation@dorsai.com (Florian Lengyel) writes:
  18.  
  19. FL:
  20. >>If you believe the polynomial-time version of Church's thesis, this situation
  21. >>cannot occur (assuming that polynomial-time means the same thing in both
  22. >>models). 
  23.  
  24. VY:
  25. >What's the polynomial-time version of Church's thesis?  Note that
  26. >a computation requiring Ackermann(1000,1000)+n steps can be carried out
  27. >in linear time, but is surely not feasably computable.
  28.  
  29. Victor, you old ne-plus-ultra-intuitionist, you took the words right
  30. out of my mouth.  Florian, I have no idea what you are talking about.
  31. None of the treatments of Church's thesis known to me seem to shed any
  32. light on your use of the term.  This is not just a matter of feasible
  33. computability being demonstrably different in its extension from
  34. polynomial-time computability, but that of the dubious relevance of
  35. issues of complexity to the matter at hand.
  36.  
  37. >yodaiken@chelm.cs.umass.edu
  38.  
  39. cordially,
  40. mikhail zeleny@husc.harvard.edu
  41. "Le cul des femmes est monotone comme l'esprit des hommes."
  42.