From: Penousal Machado <machado@eden.dei.uc.pt>
Subject: Re: Turing's diagonal argument
Date: Tue, 02 Feb 1999 15:24:17 +0000
Newsgroups: sci.math
Keywords: Halting problem for Turing machines

alewife@my-dejanews.com wrote:

> What does it mean for a Turing machine to 'halt'?

Reaching the halting state.

> How does Turing's diagonal argument (a la Cantor) imply the undec. of the
> halting problem?

The set of functions is uncountable, the set of turing machines (programs) is
countable,
therefore there are more functions than programs.
By the diagonal argument Turing proves that the existance of a TM that decides
the
halting probling is contradictory.
You can find a proof in:
    http://pass.maths.org.uk/issue5/turing/