Difference between revisions of "Halting problem"

Revision as of 04:52, February 8, 2011

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

int halts(int x) {
    while(x > 0) {
    }
}

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

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.

@@ Line 1: / Line 1: @@
-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
+ int halts(int x) {
+     while(x > 0) {
+     }
+ }
+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.
-[[Category:Computer Science]]

Difference between revisions of "Halting problem"

Revision as of 04:52, February 8, 2011

Navigation menu

Search