[FOM] Is current computability theory intuitionistic?

[joeshipman at aol.com]

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
http://www.cs.nyu.edu/mailman/listinfo/fom

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