| 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 its initial input, determine whether the program, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting.'' Alan Turing proved in 1936 that a general Algorithm to solve the halting problem for all possible inputs cannot exist. We say that the halting problem is '' Undecidable '' over Turing Machine s. ( {Link without Title} with respect to attribution of "halting problem" to Turing.) FORMAL STATEMENT One possible way of formally stating the halting problem is as follows: Given a Gödel Numbering of the Computable Function s, with the Cantor Pairing Function , | ||
| "http://wwwinformationdelightinfo/encyclopedia/entry/7_October" class="copylinks">7 October 1936 -- Paper of Emil Post is received by Church’s (Hodges p 125) ''Journal of Symbolic Logic'' His paper appeared as "Finite Combinatory Processes Formulation I",(reprinted in U p 298ff) Post's brief paper introduces the word "terminate” Church had to certify that Post was unaware of Turing's work and vice versa (cf commentary in U p 288, also Hodges p 125) See FootnotePost |
||
| January 1937 -- Turing's ''On Computable Numbers With An Application To The Entscheidungsproblem'' Is Published (reprinted In U, P 115) With Three Theorems He Answers The “decision Problem”: "I Shall Show That There Is No General Method Which Tells Whether A Given Formula '''U''' Is Provable In '''K''' | "Principia" class="copylinks" target="_blank">Mathematica , or what comes to the same, whether the system consisting of '''K''' with -'''U''' adjoined as an extra axiom is consistent" (p 145, ibid) See FootnoteTuring |
|
| '''FootnotePost''': In His Paper Post Describes A "formulation" (ie Process, Not A Machine) Consisting Of "a Worker" Who Follows A "set Of Instructions" (instructions That Are, As It Turned Out, Virtually Identical To Those Of Turing's Machines) But Post Adds Another Instruction "(C) Stop" Thus "This Process Will Terminate When And Only When It Comes To The Direction Of Type (C)" He Called Such A Process "type 1 If The Process It Determines Terminates For Each Specific Problem" He Went On To Remove The "Stop" Instruction When Evaluating "symbolic Logics" In This Case "a Deterministic Process Will Be Set Up Which Is ''unending''" | "his" class="copylinks" target="_blank">italics Post did not address directly the "Entscheidungsproblem" in his "formulation" see Post-Turing Machine for more |
|
|