[FOM] Proofs in Computability Theories

Andrej Bauer andrej.bauer at andrej.com
Fri Sep 18 19:09:23 EDT 2009

> Both theories studies machines. Like thermodynamic Carnot' theorem,
> the main theorems of compuatbility theory (e.g. the existence of the
> universal machine) are ad absurdum theorems of the weak kind, i.e..
> by concluding trough no more than a double negated sentence belonging
> to intuitionistic logic..

Could you please explain what you mean in the above paragraph, with
regards to the existence of the universal machine being proved ad
absurdum of the weak kind? I presume you are referring to the theorem
which says that there is a Turing machine which simulates all others.
The existence of such a machine is constructed very concretely, which
is why I am confused.

With kind regards,

Andrej Bauer

More information about the FOM mailing list