[FOM] Is current computability theory intuitionistic?

[Mitchell Spector]

I'm not sure about this, but aren't there some priority arguments in recursion theory in which each 
"marker" moves only finitely often, but there's no recursive bound on the function that maps n to 
the number of times marker n moves?

Mitchell Spector
E-mail: spector at alum.mit.edu



joeshipman at aol.com wrote:
> 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  <mailto:FOM at cs.nyu.edu>
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
>
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>