Construct · 1 fields · 1 citations

decidability: a standalone construct

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

● anchor · a standalone construct Nearest construct by meaning·not indexed
decidability1 CONSTRUCTDecidabilityCHURCH · 1936

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

Computability theory

An algorithm settles every instance

In computability theory, a decision problem is decidable (or recursive) if there is an algorithm that halts on every input and correctly answers yes or no; otherwise it is undecidable. Church's 1936 An unsolvable problem of elementary number theory, alongside Turing's work the same year, exhibited problems for which no such algorithm can exist, giving a negative answer to Hilbert's Entscheidungsproblem. The referent is the existence (or provable non-existence) of a total, always-correct decision procedure for a class of questions.[1]

Unit
Whether a total algorithm exists that correctly answers every instance of the problem
Recovery means
Not applicable
Measured by
Established by exhibiting a deciding algorithm, or by proving undecidability through reduction from a known undecidable problem

Next

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

See how decidability 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

satisfiability1 fields · 1 citationsanchor · a standalone constructChurch-Turing thesis1 fields · 3 citationsanchor · a standalone constructlambda calculus1 fields · 3 citationsanchor · a standalone construct

References

  1. Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58(2), 345–363. https://doi.org/10.2307/2371045

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