halting problem
Turing's result that there is no general algorithm to determine whether an arbitrary computer program will eventually halt or run forever.
As defined in ms_320
Where it comes up · 12
- 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity5 claims
- Joel David Hamkins4 claims
- 282 | Joel David Hamkins on Puzzles of Reality and Infinity3 claims
- AMA | August 20212 claims
- Grant Sanderson (@3blue1brown) — Past, present, & future of mathematics1 claim
- Joe Carlsmith — Preventing an AI takeover1 claim
- 153 - Possible Minds1 claim
- George Hotz #31 claim
and 4 more
Most important claims · 10 of 22Search all claims for “halting problem” →
- Because of Turing's 1936 results (the halting problem), it is mathematically impossible to know in advance where a program will go or what a computation will produce; each step is deterministic but the outcome is not predetermined, so the only way to know the result is to run the computation.325 | Alvy Ray Smith on Pixar, Pixels, and the Great Digital Convergence
- Although the halting problem is undecidable, it has a 'black hole': there is a computable procedure that correctly decides almost every instance, because the asymptotic density of programs whose head falls off the tape (via random-walk behavior, by Pólya's recurrence theorem) before repeating a state goes to 100% as the number of states grows.Joel David Hamkins
- Gödel's incompleteness theorem follows immediately from the undecidability of the halting problem without needing the Gödel sentence: a complete computable axiomatization of elementary mathematics would let a theorem-enumeration machine solve the halting problem by waiting for either the halt or non-halt statement, which is impossible.Joel David Hamkins
- There is a phase transition in cognitive capacity when a brain or information-processing system gains enough capacity to be a Turing machine, after which it can run essentially any computation; but finite resources in space and time mean some computations remain impossible, so the ability to create new primitives ad infinitum is overstated.AMA | March 2022
- Removing Turing completeness from a computation stack allows you to reason about things; the neural network (the ADMO machine) runs identical compute every time and only the data changes, so a branch predictor's 1% error rate stems from the halting problem — meaning you can build a stack that exploits the static, predictable nature of neural network computation.George Hotz #3
- Hamkins and Miasnikov proved that although the halting problem is undecidable, for the one-way infinite tape Turing machine model it is decidable on a set of probability one: as program size grows, the proportion of programs whose halting status can be decided approaches 100%, because by Polya's recurrence theorem a random-walking head falls off the tape with probability one, though the result is fragile because it depends on the chosen computational model.282 | Joel David Hamkins on Puzzles of Reality and Infinity
- Against the view that science is nearly complete (you get the fundamental laws and everything else is expensive but unimportant), there is a rival picture where discovery is ongoing and incomplete—even with basic laws, locating useful technologies at the macro scale remains a vast search problem—implying more diversity of tech across the universe, more ongoing churn and upheaval, and less civilizational lock-in; moreover full knowledge may be impossible because the knower is part of the system being modeled.Joe Carlsmith — Preventing an AI takeover
- Real artificial intelligence will by definition be non-algorithmic and therefore uncontrollable; the belief that we can program and control AI is provably wrong, much as Turing's halting problem showed there is no systematic way to inspect code and predict what it will do, so the only realistic stance is to expect not to have control.153 - Possible Minds
- Conway's Game of Life is a playground for computably undecidable questions: the question of whether a given cell will ever become alive in the evolution of a configuration is equivalent to the halting problem and is computably undecidable, though semi-decidable (if it becomes alive you find out at a finite stage).Joel David Hamkins
- There is no computable procedure that correctly answers, for all programs, whether the program will halt; one can always get the yes answers by running the program, but giving the no answers requires deep insight into the program's behavior, and a diagonal argument shows a contradiction arises if a halting decider existed.Joel David Hamkins