Linked from

The 14 pages that link to Decidability, each with the reason it gives.

• Alan TuringNarrower topic: Turing’s halting result sharply separates decidable problems from undecidable ones.

• AlgorithmRelated: Some precisely stated problems have no algorithmic solution at all.

• Computability theoryRelated: It names the central distinction between solvable and unsolvable decision problems.

• Automated theorem provingRelated: It distinguishes logics with guaranteed decision procedures from those requiring unbounded search.

• Formal systemRelated: A formal theory may have no general procedure deciding whether every statement is a theorem.

• Law of Excluded MiddleRelated: For a proposition with decidable truth, excluded middle can be established constructively.

• CompletenessCompared with: A complete proof system need not provide an algorithm for finding proofs or deciding validity.

• Independence (mathematical logic)Compared with: Independence of one sentence is distinct from whether a theory’s consequence problem is algorithmically decidable.

• Deductive systemRelated: For a deductive system, it asks whether theoremhood can be settled algorithmically.

• Automata theoryRelated: Automata models distinguish decidable language questions from undecidable ones.

• Computable setNarrower topic: A set is computable precisely when its membership problem is decidable.

• Cut-elimination theoremRelated: For some logics, cut-free proof search helps decide whether a conclusion is derivable.

• Automated reasoningRelated: Undecidable theories place fundamental limits on complete automated decision procedures.

• Lindenbaum's lemmaRelated: A maximal consistent set decides each sentence, though this need not be an effective decision procedure.