Re: Logic and Mathematicians

Article View: sci.logic

Article #541

#541

From: victor yodaiken
Date: Thu, 19 Nov 1992 16:56

13 lines
998 bytes

In article <1992Nov16.222220.7956@dorsai.com> mutation@dorsai.com (Florian Lengyel) writes:
>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). 

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.

-- 

yodaiken@chelm.cs.umass.edu

Technical Details

Message-ID: <56452@dime.cs.umass.edu>

Path: arc1-ca.pugleaf.net!sparky!uunet!news.gtech.com!noc.near.net!nic.umass.edu!dime!chelm.cs.umass.edu!yodaiken

References: <1992Nov15.191744.17481@husc3.harvard.edu> <1992Nov16.222220.7956@dorsai.com>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!sparky!uunet!news.gtech.com!noc.near.net!nic.umass.edu!dime!chelm.cs.umass.edu!yodaiken
From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
Newsgroups: sci.logic,sci.math
Subject: Re: Logic and Mathematicians
Message-ID: <56452@dime.cs.umass.edu>
Date: 19 Nov 92 16:56:46 GMT
References: <1992Nov15.191744.17481@husc3.harvard.edu> <1992Nov16.222220.7956@dorsai.com>
Sender: news@dime.cs.umass.edu
Followup-To: sci.logic
Organization: University of Massachusetts, Amherst
Lines: 14

Reply to Parent Message