In computability theory, the halting problem is a decision problem which can be stated as follows: Given a description of a program, decide whether the program finishes running or continues to run, and will thereby run forever. This 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.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible programinput pairs cannot exist. We say that the halting problem is undecidable over Turing machines.
B. Jack Copeland (2004) attributes the actual term halting problem to Martin Davis.^{[1]}
Contents
Formal statement
The halting problem is a decision problem about properties of computer programs on a fixed Turingcomplete model of computation. The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations of memory or time on the program's execution; it can take arbitrarily long, and use arbitrarily much storage space, before halting. The question is simply whether the given program will ever halt on a particular input.
For example, in pseudocode, the program
does not halt; rather, it goes on forever in an infinite loop. On the other hand, the program
halts very soon.
The halting problem is famous because it was one of the first problems proven algorithmically undecidable. This means there is no algorithm which can be applied to any arbitrary program and input to decide whether the program stops when run with that input.
Full article ▸
