Wednesday, April 7, 2010

Unsolvable Problem

Jack Dikian
October 1999

The Halting Problem is one of the simplest problems known to be unsolvable. Given a program and an input to the program (input-program pair), determine if the program will eventually stop when it is given that input.

Turing pondered if there was a way of telling in general once a computer has embarked on a calculation whether that calculation will terminate in an answer. This problem is known as the "Halting Problem for Turing Machines" and was first proved in the 1937 paper in which he described his machines.

My interest in this was caught when writing a Turing Machine simulator and was fascinated by the seemingly simple challenge – and Turing’s elegant solution.


Briefly, a Turing machine can be thought of as a black box, which performs a calculation of some kind on an input number. If the calculation reaches a conclusion, or halts then an output number is returned. Otherwise, the machine theoretically just carries on forever. The problem is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever.

There are an infinite number of Turing machines, as there are an infinite number of calculations that can be done with a finite list of rules. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines.
Break here

Download author's Turing Machine simulator and article "Halting Problem Made Simple, October 1999"

No comments:

Post a Comment