Halting problem (nonfiction): Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[File:Halting_problem.svg|250px|thumb|Halting problem diagram.]]In computability theory, the '''halting problem''' is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. See [[Computation (nonfiction)]]. | [[File:Halting_problem.svg|250px|thumb|Halting problem diagram.]]In computability theory, the '''halting problem''' is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. See [[Computation (nonfiction)]]. | ||
[[Alan Turing|Alan Turing]] proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. | [[Alan Turing (nonfiction)|Alan Turing]] proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. | ||
A key part of the proof was a mathematical definition of a computer and program, which became known as a [[Turing machine (nonfiction)|Turing machine]]; the halting problem is undecidable over Turing machines. | A key part of the proof was a mathematical definition of a computer and program, which became known as a [[Turing machine (nonfiction)|Turing machine]]; the halting problem is undecidable over Turing machines. | ||
| Line 11: | Line 11: | ||
<gallery mode="traditional"> | <gallery mode="traditional"> | ||
File:Companion of Asclepius Myrmidon.jpg|link=Asclepius Myrmidon|[[Asclepius Myrmidon]] finds Halting problem, forecasts multiple casualties from [[Pi disaster]]. | File:Companion of Asclepius Myrmidon.jpg|link=Asclepius Myrmidon|[[Asclepius Myrmidon]] finds Halting problem, forecasts multiple casualties from [[Pi disaster]]. | ||
Forbidden_Ratio_symbol.jpg|link=Forbidden Ratio|Supervillains [[Forbidden Ratio]] and [[Gnotilus]] form [[Crime team (nonfiction)|crime team]] to destroy the [[Golden ratio (nonfiction)|Golden ratio]]. | |||
</gallery> | </gallery> | ||
Revision as of 10:34, 20 June 2016
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. See Computation (nonfiction).
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines.
It is one of the first examples of a decision problem.
In the News
Asclepius Myrmidon finds Halting problem, forecasts multiple casualties from Pi disaster.
Supervillains Forbidden Ratio and Gnotilus form crime team to destroy the Golden ratio.
Fiction cross-reference
Nonfiction cross-reference
- Halting problem @ Wikipedia