[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