Changes

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

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) {

  int halts(int x) {

     while(x > 0) {

     while(x > 0) {

halts for all valid input less than or equal to 0, and continues forever for all such input greater than 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.

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.