[FOM] Re: Comment on Church's Thesis

[Robin Adams]

On Wed, 7 Jan 2004, Robert Black wrote:

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

The situation is a little more interesting than that.  We can ask four
questions:

1. Is it Turing-decidable whether a given Turing machine halts with a 
   given input?
2. Is it effectively decidable whether a given Turing machine halts with a 
   given input?
3. Is it Turing-decidable whether a given algorithm halts with a given 
   input?
4. Is it effectively decidable whether a given algorithm halts with a 
   given input?

Questions 1 and 4 can be answered negatively without using Church's
thesis, as you have said.  The answer to 1 is the proof in all the
textbooks.  We can also give an informal argument showing the anwer to 
question 4 to be "No".

It is question 2 that requires Church's thesis for us to answer with the
diagonal argument.  And we need Church's thesis just to ask question 3:  
the question itself presupposes some way of coding an informal algorithm
as the input to a Turing machine.

So I take Adammo's original inquiry to be: is there any known way of 
answering question 2 without using Church's thesis?  I am quite certain 
there is not.  This is perhaps surprising, as (to me, at least) at first 
sight question 2 looks as if it should be easier to answer than question 
4.

-- 
Robin Adams