[FOM] Re: Comment on Church's Thesis
Robin Adams
radams at maths.man.ac.uk
Wed Jan 7 13:41:18 EST 2004
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
More information about the FOM
mailing list