[FOM] Is current computability theory intuitionistic?

joeshipman at aol.com joeshipman at aol.com
Tue Jun 18 14:36:40 EDT 2013

I can imagine a proof of the form "Algorithm X for problem Y runs in polynomial time and makes only finitely many errors, therefore problem Y is in P because a finite modification of algorithm X solves Y and runs in polynomial time". Such a proof does not seem to be translatable into an intuitionistic proof that Y is in P if there is no known computable bound on the errors. But I don't recall any specific proofs that use the "we can ignore finitely many errors" technique.

-- JS

-----Original Message-----
From: Steve Stevenson <steve at clemson.edu>
To: Foundations of FOM <fom at cs.nyu.edu>
Sent: Tue, Jun 18, 2013 1:59 pm
Subject: [FOM] Is current computability theory intuitionistic?

I didn't know to ask this question when I was learning and now I'm too
old to read all the standard books. My recollection though is that
computability texts use classical logic. Is that true? Does it matter?

D. E. (Steve) Stevenson, PhD, Emeritus Associate Professor, Clemson University
"Those that know, do. Those that understand, teach," Aristotle.
FOM mailing list
FOM at cs.nyu.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130618/e467a59b/attachment.html>

More information about the FOM mailing list