[FOM] Re: Comment on Church's Thesis

[Robert Black]

>Do you or anybody know a proof of the undecidability of the Halting problem
>not depending on Church's Thesis?
>
>Adam

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.

Robert

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