(New page: In computability theory, the halting problem is a decision problem which can be stated as follows: A description of a program and a finite input, decide whether the program finishes runnin...) |
|||
| Line 1: | Line 1: | ||
In computability theory, the halting problem is a decision problem which can be stated as follows: | In computability theory, the halting problem is a decision problem which can be stated as follows: | ||
A description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. | A description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. | ||
| − | Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines. Copeland (2004) attributes the actual term halting problem to Martin Davis. | + | Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines. Copeland (2004) attributes the actual term halting problem to Martin Davis.--[[User:Kim297|Kim297]] 10:14, 20 November 2008 (UTC) |
Revision as of 06:14, 20 November 2008
In computability theory, the halting problem is a decision problem which can be stated as follows: A description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines. Copeland (2004) attributes the actual term halting problem to Martin Davis.--Kim297 10:14, 20 November 2008 (UTC)
