halting problem

Related Overviews

decision problem

Turing machine

Alan Turing (1912—1954) mathematician and computer scientist


More Like This

Show all results sharing this subject:

  • Computing


Show Summary Details

Quick Reference

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.

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.