Halting problem (nonfiction): Difference between revisions
| Line 13: | Line 13: | ||
File: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]]. | File: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]]. | ||
File:Mathematical function.svg|link=Mathematical function (nonfiction)|Law-abiding [[Mathematical function (nonfiction)|mathematical functions]] have nothing to fear from [[Crimes against mathematical constants]], say crime authorities. | File:Mathematical function.svg|link=Mathematical function (nonfiction)|Law-abiding [[Mathematical function (nonfiction)|mathematical functions]] have nothing to fear from [[Crimes against mathematical constants]], say crime authorities. | ||
File:Halting problem.svg|link=Halting problem (nonfiction)|Unregistered [[Halting problem (nonfiction)|Halting problems]] used in [[Crimes against mathematical constants]], says [[Asclepius Myrmidon]]. | |||
</gallery> | </gallery> | ||
Revision as of 09:38, 21 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.
Law-abiding mathematical functions have nothing to fear from Crimes against mathematical constants, say crime authorities.
Unregistered Halting problems used in Crimes against mathematical constants, says Asclepius Myrmidon.
Fiction cross-reference
Nonfiction cross-reference
- Halting problem @ Wikipedia