home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / logic / 2104 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  1017 b 
  1. Xref: sparky sci.logic:2104 sci.math:15240
  2. Path: sparky!uunet!news.gtech.com!noc.near.net!nic.umass.edu!dime!chelm.cs.umass.edu!yodaiken
  3. From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
  4. Newsgroups: sci.logic,sci.math
  5. Subject: Re: Logic and Mathematicians
  6. Message-ID: <56452@dime.cs.umass.edu>
  7. Date: 19 Nov 92 16:56:46 GMT
  8. References: <1992Nov15.191744.17481@husc3.harvard.edu> <1992Nov16.222220.7956@dorsai.com>
  9. Sender: news@dime.cs.umass.edu
  10. Followup-To: sci.logic
  11. Organization: University of Massachusetts, Amherst
  12. Lines: 14
  13.  
  14. In article <1992Nov16.222220.7956@dorsai.com> mutation@dorsai.com (Florian Lengyel) writes:
  15. >If you believe the polynomial-time version of Church's thesis, this situation
  16. >cannot occur (assuming that polynomial-time means the same thing in both
  17. >models). 
  18.  
  19. What's the polynomial-time version of Church's thesis?  Note that
  20. a computation requiring Ackermann(1000,1000)+n steps can be carried out
  21. in linear time, but is surely not feasably computable.
  22.  
  23. -- 
  24.  
  25.  
  26. yodaiken@chelm.cs.umass.edu
  27.  
  28.