[FOM] Proofs in Computability Theories

Carl Mummert mummertc at marshall.edu
Sat Sep 19 13:01:49 EDT 2009

On Tue, Sep 15, 2009 at 7:27 PM, Steve Stevenson <steve at cs.clemson.edu> wrote:
> 1. Shouldn't the study of computability be constructive - thinking of
> Markov, and
> 2. Shouldn't the proofs therefore be intuitionistic?

If we identify computability with the study of effective calculation
then there is certainly some appeal to using only constructive
methods, because of the informal meaning of the word "effective".

However, to the extent that classical computability theory is the
study of definability of subsets of the natural numbers and classes of
such subsets, we should apply the same standards to computability
theory that we apply to the study of the natural numbers themselves.
>From that perspective, the issue of constructivism in classical
computability theory is really the same as the issue of constructivism
in arithmetic.

Best regards,


More information about the FOM mailing list