[FOM] Church thesis

José Félix Costa fgc at math.ist.utl.pt
Wed Jan 7 03:45:11 EST 2004

Of course Addamo.
The proof of the halting problem FOR Turing machines or FOR the register
machine, or... does not depend on the Church thesis.

Such a proof can be find in the book by

John Bell and Moshe Machover
A Course in Mathematical Logic
North-Holland, Second printing 1997

Chapter 6 is enough for a reading.

Page 259 comments on this: When doing recursion theory, we shall not use
Church Thesis in our proofs.

Proof you wish in page 271.

Best regards,


J. Felix Costa
Departamento de Matematica
Instituto Superior Tecnico
Av. Rovisco Pais, 1049-001 Lisboa, PORTUGAL
tel:      351 - 21 - 841 71 45
fax:     351 - 21 - 841 75 98
e-mail:   fgc at math.ist.utl.pt
www:    http://fgc.math.ist.utl.pt/jfc.htm

More information about the FOM mailing list