🚀 go-pugleaf

In article <56452@dime.cs.umass.edu> 
yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:

>In article <1992Nov16.222220.7956@dorsai.com> 
>mutation@dorsai.com (Florian Lengyel) writes:

FL:
>>If you believe the polynomial-time version of Church's thesis, this situation
>>cannot occur (assuming that polynomial-time means the same thing in both
>>models). 

VY:
>What's the polynomial-time version of Church's thesis?  Note that
>a computation requiring Ackermann(1000,1000)+n steps can be carried out
>in linear time, but is surely not feasably computable.

Victor, you old ne-plus-ultra-intuitionist, you took the words right
out of my mouth.  Florian, I have no idea what you are talking about.
None of the treatments of Church's thesis known to me seem to shed any
light on your use of the term.  This is not just a matter of feasible
computability being demonstrably different in its extension from
polynomial-time computability, but that of the dubious relevance of
issues of complexity to the matter at hand.

>yodaiken@chelm.cs.umass.edu

cordially,
mikhail zeleny@husc.harvard.edu
"Le cul des femmes est monotone comme l'esprit des hommes."