Re: proof of undecidability of halting problem
- From: "Charlie-Boo" <shymathguy@xxxxxxxxx>
- Date: 14 May 2006 20:04:24 -0700
Patricia Shanahan wrote:
Per Freem wrote:
hi all,
the usual proof of the undecidability of the halting problem does so by
reductio ad absurdum. i understand that if we assume that we have a
function halt(i, s) that returns true if the if p describes a program
that halts when given as input the string i, and false otherwise, we
get a contradiction.
however, the contradiction is introduced by using a second function,
defined as follows:
function trouble(string s)
if halt(s, s) == false
return true
else
loop forever
if we then let t be the string representing trouble, then if trouble(t)
halts we get a contradiction and if it doesn't halt we also get a
contradiction.
i understand this and i have no problem with the self-reference aspect.
but how do we know, in this proof, that the right conclusion is not
then to say that a function like trouble cannot exist, rather than that
a function like halt can't? in other words how do we know that the
source of contradiction was really the assumption that halt exists?
For really understanding this, it is worth while dropping down from the
pseudo-code level to the Turing machine (TM) level.
You are right to ask whether there is proof that "trouble" can be
implemented. It was not obvious that a TM can simulate the operation of
another TM with given input. However, Turing proved it could be done. If
you want to learn more about this, look up "Universal Turing Machine".
Of course, since then we have got so used to simulating computers on
other computers etc. that it is easy to miss the fact that the existence
of UTMs ever needed to be proved. Informal discussions of the halting
problem, even in TM contexts, tend to skip that step.
And don't stop there, please. What other high level parallels are
there between Turing/Godel and everyday use of a computer by
programmers and users? How can a high level language prove theorems
e.g. Recursion Theory is a snap.
C-B
The rest of the implementation of "trouble" as a TM is relatively simple.
Patricia
.
- References:
- proof of undecidability of halting problem
- From: Per Freem
- Re: proof of undecidability of halting problem
- From: Patricia Shanahan
- proof of undecidability of halting problem
- Prev by Date: Re: Why? [was Re: Cantor`s powerset theorem is false?]
- Next by Date: Re: Liar's Paradox in Godel's Theorem (newbie question)
- Previous by thread: Re: proof of undecidability of halting problem
- Next by thread: Re: proof of undecidability of halting problem
- Index(es):
Relevant Pages
|
