| Halting Problem |
Website Links For Problem |
Information AboutHalting Problem |
| CATEGORIES ABOUT HALTING PROBLEM | |
| mathematical logic | |
| theory of computation | |
| recursion theory | |
Given 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 Machine s. (See In none of his work did Turing use the word "halting" or "termination". Turing's biographer Hodges does not have the word "halting" or words "halting problem" in his index. The earliest known use of the words "halting problem" is in a proof by Davis (p. 70-71, Davis 1958). ::"Theorem 2.2 ''There exists a Turing machine whose halting problem is recursively unsolvable''. :"A related problem is the ''printing problem'' for a simple Turing machine Z with respect to a symbol Si" (p. 70). Davis adds no attribution for his proof, so one infers that it is original with him. But Davis has pointed out that a statement of the proof exists informally in Kleene (1952) on page 382. Copeland (2004) states that: : "The halting problem was so named (and it appears, first stated) by Martin Davis Copeland footnote 61 ... (It is often said that Turing stated and proved the halting theorem in 'On Computable Numbers', but strictly this is not true)." (p. 40) For more see the History section above. FORMAL STATEMENT A Decision Problem is a set of natural numbers; the "problem" is to determine whether a particular number is in the set. Given a Gödel Numbering of the Computable Function s (such as Turing's Description Number s) and a Pairing Function , the halting problem (also called the '''halting set''') is the decision problem for the set |
|
|