[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,

Felix

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