Is it Possible for Turing Machines to Solve the Halting Problem?

By

Home / Is it Possible for Turing Machines to Solve the Halting Problem?

The Impossibility of Solving the Halting Problem: The Programmer’s Proof

A Computer Magnetic Tape Drive is like a Turing Machine, by Steve Parker

A Computer Magnetic Tape Drive is like a Turing Machine, by Steve Parker

The Halting Problem actually cannot be solved, as demonstrated by a “proof by contradiction.” This is a non-technical summary of the proof as a computer programmer might express it.

Let HPM be the Turing machine that is supposed to solve the Halting Problem. Let UM be the “Unsolvable Machine,” or the one that will cause the HPM to fail. The UM itself is an adaptation of a UTM, and its actions depend on the instructions of the HPM.

If the HPM could succeed, it would look like this: The HPM would read the UM’s encoded instructions, plus whatever input the UM would read, and after a finite number of steps, the HPM would report either “Yes, the UM will halt” or “No, the UM will not halt”.

When put to the test, however, this UM will behave as a UTM, and will read the HPM’s encoded instructions as its input, then read its own UM code as the secondary input, and finally emulate the HPM’s processes until the HPM makes its report.

If the UM process shows that the HPM would report “Yes, the UM will halt,” then the UM’s instructions are to instead begin a loop, repeating the message that it will never halt, in direct contradiction of what the HPM expects.

If the UM determines that the HPM would report “No, the UM will not halt,” then the UM will instead write the message that it is halting, and do so – again, its instructions cause it to contradict the HPM.

The HPM is not allowed to be “clever” enough to report that the UM is programmed to do the opposite of what it predicts; the only valid responses are the predictions “will halt” or “will not halt”. If the HTM cannot make its prediction in a finite number of steps, then it also fails to meet the criteria.

By calculating what the HTM predicts it to do, and then doing the opposite, the UM can foil any proposed Turing machine that is supposed to be able to solve the Halting Problem.

Leave a Comment