Changes

The '''Halting Problem''' is a problem in theoretical [[computer science]] which measures the effectiveness with which [[computer]]s execute [[algorithm]]s. In the theoretical formulation, computers are represented by [[Turing machine]]s and algorithms are represented by an infinitely long piece of tape that moves around inside the Turing machine. The tape has instructions for the machine; if it can execute this instruction it moves to the next piece of tape, if it cannot, the machine halts. The Halting Problem asks for a reliable prediction of whether a particular machine will halt before you put the tape into it.

The '''halting problem''', a subject in theoretical [[computer science]] is the general question of determining, given a description of a [[computer program]], and a given input to said program, whether the program will come to an end (halt) on a Turing-complete machine, or continue to run forever. For example, it is apparent that the program described by the C snippet

halts for all valid input less than or equal to 0, and continues forever for all such input greater than 0.

[[Alan Turing]], the founding father of theoretical computer science, showed the Halting Problem is [[undecidable]]. In other words, one can never truly rely on a computer to halt its computations. While this is theoretically significant, in practice most computer programs have been written so that they do not have [[runtime error]]s.

In 1936, [[Alan Turing]] proved that there is no general algorithm that can decide this for every possible program and every possible input. (In other words, it is impossible to write a program that is capable of deciding whether a given program and given input will halt in all cases -- there will be some for which it is impossible for it to make such a determination.) As such, the halting problem is [[undecidable]] over Turing machines.