Re: Turing's Halting Algorithm Question

From: Ajoy K Thamattoor (ajoyk_at_cs.stanford.edu)
Date: 12/24/04 

Date: Fri, 24 Dec 2004 13:33:48 -0800
To: phl <killkennyhouse@hotmail.com>

phl wrote:
> Hi
>
> I have been trying to understand the basics of Turing machines and I am
> having some problem understanding the halting algorithm. The book I
> have states that last two instructions are:
>
> -If U(Universal Turing machine) stops with input data d+d (where
> d=code(Program)), repeat this step indefintely.
>
> -If U does not stop with with input data d+d, then stop.
>
> How is this done in practice?

        It can't be. Not just in practice. Even in theory. There is no
halting algorithm. In other words, there is no algorithm which can tell
you if an arbitrary Turing Machine will ever halt on an arbitrary input.
The proof is typically a reduction from the acceptance problem - if you
can figure out whether an arbitrary TM/input pair is going to halt or
not, you can actually figure out whether an arbitrary TM is going to
accept an arbitrary input string. And this is known to be impossible.
One version of the formal proof depends on a diagonalization
argument. Informally, this boils down to a paradox which dates to
Babylonian times - the statement 'I am a liar' can never be either true
or false. In any discrete system, such statements will exist, and no
algorithm can ever determine the truth of such a statement.

Ajoy.