Halting problem (nonfiction): Difference between revisions
Jump to navigation
Jump to search
(Created page with "[[File:]]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...") |
No edit summary |
||
| Line 1: | Line 1: | ||
[[File:]]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|Alan Turing]] proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. | ||
Revision as of 10:26, 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.
Fiction cross-reference
Nonfiction cross-reference
- Halting problem @ Wikipedia