Construct · 1 fields · 2 citations

halting problem: a standalone construct

One name. One construct. A landmark on the map.

● anchor · a standalone construct Nearest construct by meaningTuring machinecompare the meanings
How to read this

Every construct on the map is compared with every other by the meaning of its definitions, and the closest one is surfaced here. The nearest construct to halting problem is Turing machine.

Hold this as a prompt, not a verdict. Two constructs sitting close in meaning is a reason to read them side by side and decide for yourself whether they are one idea under two names. It is not proof that they are. Compare the meanings in the Collider.

haltingproblem1 CONSTRUCTHalting problemTURING · HALTING

A single standalone construct; nearby constructs are located against it in the Collider. Tap a field for its definition, unit, and measures.

Computability theory

The undecidability of whether an arbitrary program halts on a given input

Alan Turing's 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem proved that no single procedure can decide, for every possible program and every input, whether that program will eventually stop running or instead continue forever. Turing reasoned about an idealised computing device, now called a Turing machine, and showed by a self-referential argument that assuming a universal decider for halting exists leads to a contradiction. The property later took the name the halting problem in Martin Davis's 1958 book Computability and Unsolvability, where it stands as the standard example of an undecidable problem, one for which no algorithm can return a correct yes-or-no answer in all cases. What makes the halting problem a landmark is its generality: many other questions in logic and computer science are shown to be unanswerable by proving that solving them would also solve halting, so it serves as a fixed reference point for the limits of what computation can decide.[1][2]

Unit
A decision problem about programs, classified as decidable or undecidable
Recovery means
Not applicable
Measured by
Established by mathematical proof, typically by diagonalization or by reducing a known undecidable problem to it, not by empirical measurement

Next

Run it through the Collider, or take the citations with you.

See how halting problem sits against neighbouring constructs in the Collider, or export every reference on this page in one click.

Open in ColliderExport BibTeXReport this entry

Nearby constructs

recursion4 fields · 8 citationsjingle · one word, four self-referring constructsChurch-Turing thesis1 fields · 3 citationsanchor · a standalone constructTuring machine1 fields · 3 citationsanchor · a standalone construct

References

  1. Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42(1), 230–265. https://doi.org/10.1112/plms/s2-42.1.230
  2. Davis, M. (1958). Computability and unsolvability. McGraw-Hill.

Cited on this page?

Confirm your construct, or correct us.

If your work is cited behind one of these entries, you know better than we do whether we captured the meaning right. Confirm it, suggest an edit, or dispute it, and your name goes on the entry as an author who has checked it, linked to your ORCID.

Claim your construct