Re: Disproof of the Halting Problem's Conclusion

From: Isaac To (iketo2_at_netscape.net)
Date: 07/24/04 

Date: 24 Jul 2004 23:45:57 +0800

>>>>> "Peter" == Peter Olcott <olcott@worldnet.att.net> writes:

    Peter> All that Turing's proof showed was that you can not
    Peter> construct a halt analyzer that returns its result back to
    Peter> the program being analyzed. This has been taken to mean
    Peter> (but does not mean) that

    Peter> No program can ever be written to determine whether any
    Peter> arbitrary program will halt.

There are two "program"s in your sentences above, and I assume that
you mean that the first "program" is not more powerful than Turing
machines; and the second "program" is not weaker (e.g., you do not
mean that "No program can ever be written to determine whether any
finite automata will halt").

Your description suggests that the proof that "halting problem for
Turing machines is unsolvable using Turing machines" is "interpreted"
further without much thoughts. This is not the truth.

What theoreticians "interpret" is instead that

  The halting problem for any type of machine capable of expressing
  the Turing machine computations cannot be solved using any type of
  machine that the Turing machine is capable of expressing.

Here "a machine of type A capable to express a machine of type B"
means we can, using a Turing machine, mechanically convert a machine
of type A to a machine of type B.

E.g., in order to prove that the halting problem is unsolvable in the
context of "Random Access Machine" (RAM), i.e., a machine similar to a
Turing machine but with the addition of Random access memory, then one
would have to prove that (1) there is a Turing machine which converts
every Turing Machine to an equivalent RAM; and then (2) there is a
Turing machine which converts every RAM to an equivalent Turing
Machine. Both of these can be done, so the above "interpretation"
works to show that the halting problem is unsolvable in RAM. Note
that theoreticians *don't* "rerun" the arguments of the halting
problem unsolvability proof of the Turing machine in the context of
RAM. It is unnecessary, and it is not guaranteed to be possible.

Why the above "interpretation" is correct? It is simple logic: if
such a machine exists, then we would have a Turing machine that solve
the halting problem for the Turing machines. The machine would
consists of a stage to convert the input Turing machines into the
equivalent machine of the "stronger" type. Then, after the input is
"assimilated", a Turing machine (simulator of the halting solver in
another context) is used to run on that modified input. But we
already know that such Turing machines cannot exist, so we have a
contradiction. (Technically, there doesn't need to be a Turing
machine to create the simulator, the mere existance of the simulator
is sufficient for the impossibility of halting solver to carry over.)

I leave it to you as an exercise to check that your machines indeed
can be simulated using a Turing machine, and thus have no power to
solve the halting problem for any Turing-equivalent machines
(including regular programs if we assume infinite memory).

Regards,
Isaac.

Relevant Pages

  • Re: Disproof of the Halting Problems Conclusion
    ... Peter> the computer making the program not run correctly. ... But as long as you modify your program correctly, ... Halting problem: once you know that the halting problem of Turing ... Turing machine) cannot be solved using anything with no stronger power ...
    (comp.theory)
  • Re: Disproof of the Halting Problems Conclusion
    ... Peter> the computer making the program not run correctly. ... But as long as you modify your program correctly, ... Halting problem: once you know that the halting problem of Turing ... Turing machine) cannot be solved using anything with no stronger power ...
    (sci.logic)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (sci.logic)
  • Re: Exploiting limitations of Turing machines in Turing tests?
    ... correctly answer _any_ halting problem question. ... You were proposing that there exists some finite set of special Turing ... able to successfully answer _all_ halting problem questions. ... It's a description of some Turing Machine, and some input, with the simple ...
    (comp.ai.philosophy)