[FOM] Re: Comment on Church's Thesis
Mongre at gmx.de
Wed Jan 7 03:06:53 EST 2004
>Do you or anybody know a proof of the undecidability of the Halting problem
>not depending on Church's Thesis?
I don't think you need Church's thesis to prove the undecidability of
the halting problem. Just staying within the intuitive notion of
'effectively computable function' the obvious diagonalization shows
that the effectively computable total functions aren't effectively
enumerable. But the procedures for computing partial functions are
effectively enumerable (they have to be for the halting problem to be
statable in the form: does the nth procedure applied to input m
terminate?) and the assumption of the decidability of the halting
problem now leads easily to a contradiction (replace each partial
function by the corresponding total function taking the value zero
where the partial function was undefined).
Obviously you don't need Church's thesis to prove that the halting
problem for Turing machines isn't Turing-machine decidable. What you
do need it for is to tell you that the two results you have now
proved are really one and the same.
PS I am at present in Berlin, which is why this message is coming
from a gmx address. But you can reply to my usual
<Robert.Black at nottingham.ac.uk>.
More information about the FOM