Re: proof of undecidability of halting problem

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.

The rest of the implementation of "trouble" as a TM is relatively simple.

Patricia
.

Relevant Pages

  • Re: Why isnt James Harris working oh halting problem?
    ... Of course it is odd. ... Obviously B cannot halt only ... If the halting problem were solvable, ... that is a contradiction, so the halting problem ...
    (sci.math)
  • Re: Why isnt James Harris working oh halting problem?
    ... halt, so B cannot exist. ... If the halting problem were solvable, ... that is a contradiction, so the halting problem ... The irrationality proof of sqrtdoes not show that integers ...
    (sci.math)
  • Re: proof of undecidability of halting problem
    ... the usual proof of the undecidability of the halting problem does so by ... however, the contradiction is introduced by using a second function, ... if we then let t be the string representing trouble, ... a function like halt can't? ...
    (sci.logic)
  • Re: proof of undecidability of halting problem
    ... the usual proof of the undecidability of the halting problem does so by ... however, the contradiction is introduced by using a second function, ... a function like halt can't? ...
    (sci.logic)
  • Re: proof of undecidability of halting problem
    ... the usual proof of the undecidability of the halting problem does so by ... however, the contradiction is introduced by using a second function, ... if we then let t be the string representing trouble, ... a function like halt can't? ...
    (sci.logic)
Quantcast