halting problem

views updated

halting problem A decision problem that was discovered and investigated by Alan Turing in 1936. Suppose M is a Turing machine and let x be an input to M. If we start the machine running two things might happen: after a finite number of steps the machine might stop, or it might run on forever. Is there any way to test, given M and x, which of these two situations will occur? This is the halting problem. In fact there is no algorithm or effective procedure that, given any Turing machine and its input, will decide whether or not the calculation ever terminates.

Assuming the Church–Turing thesis, the halting problem is algorithmically unsolvable or undecidable. It is one example of many unsolvable problems in mathematics and computer science. It has profound practical implications: if it were solvable it would be possible to write a program tester that, given (say) any Pascal program and its input, would print “yes” if the program terminated after a finite number of steps and “no” if it did not. For any programming language that can define the recursive functions, no such termination program exists.