[FOM] Is current computability theory intuitionistic?

Alasdair Urquhart urquhart at cs.toronto.edu
Tue Jun 18 17:41:21 EDT 2013

Current texts certainly do present computability in terms of classical
logic.  I recall some example in Hartley Rogers along the lines
of a function defined by: f(n) = 1 if the Riemann hypothesis is true,
otherwise 0 (I don't have the book at hand right now).  Rogers
says that f is a well defined function.

Whether this matters or not, I am not sure.  I think a lot of 
computability theory can be easily reworked in a constructive context, 
since the arguments are generally constructive.  On the other hand,
the classical arithmetical hierarchy presupposes a classical
reading of the quantifiers.

On Tue, 18 Jun 2013, Steve Stevenson wrote:

> 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.

More information about the FOM mailing list