The halting problem is a decision problem about properties of computer programs on a fixed Turing- complete model of computation, i.e. all programs that can be written in some given programming language that is general enough to be equivalent to a Turing machine. 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 on the amount of memory or time required for 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:
while (true) continue;
does not halt; rather, it goes on forever in an infinite loop. On the other hand, the program
print “Hello, world!”
halts very quickly.
While deciding whether these programs halt is simple, more complex programs prove problematic.
One approach to the problem might be to run the program for some number of steps and check if it halts. But if the program does not halt, it is unknown whether the program will eventually halt or run forever.
Turing proved there cannot exist an algorithm which will always correctly decide whether, for a given arbitrary program and its input, the program halts when run with that input; the essence of Turing’s proof is that any such algorithm can be made to contradict itself, and therefore cannot be correct.