Linked from

The 28 pages that link to Computability theory, each with the reason it gives.

• Turing machineNarrower topic: Turing machines provide a central language for classifying computable problems.

• Alan TuringNarrower topic: Turing’s work helped establish its limits and foundational questions.

• Halting problemNarrower topic: The halting problem is a foundational example of an unsolvable computational problem.

• Automated theorem provingRelated: Its limits explain why general theorem proving cannot be both complete and always terminating.

• Principia MathematicaRelated: Later work on formal systems and decision problems grew from questions sharpened by foundational projects.

• Proof theoryCompared with: It focuses on effective procedures, though proof systems can encode computational limits.

• Mathematical logicBroader topic: It connects formal reasoning to algorithms and the limits of computation.

• Alonzo ChurchNarrower topic: Church’s work helped establish this field by giving a formal account of effective computation.

• Kurt GödelRelated: Gödel’s proof uses effectively describable formal rules and relations between statements and proofs.

• Decision problemNarrower topic: Decision problems are a central way computability theory formulates questions of solvability.

• EntscheidungsproblemNarrower topic: The impossibility proof helped establish computation’s formal limits as a mathematical subject.

• Kolmogorov complexityNarrower topic: Limits of computation explain why exact Kolmogorov complexity cannot be calculated in general.

• Computable functionNarrower topic: It classifies computable functions and studies the limits of algorithms.

• Formal logicNarrower topic: Formal logic supplied central questions and methods for studying computation's limits.

• FormalismRelated: Formal derivations connect mathematical proof to effective, rule-governed computation.

• Philosophy of mathematicsRelated: It clarifies the limits of effective mathematical procedures.

• Algorithmic information theoryNarrower topic: Uncomputability sets fundamental limits on calculating exact Kolmogorov complexity.

• Automata theoryNarrower topic: Turing-machine automata provide the central model for defining algorithmic solvability.

• Kleene's recursion theoremNarrower topic: The recursion theorem is a foundational result about effective computation and program indices.

• Formal scienceRelated: It establishes formal limits on what computation can accomplish.

• Julia RobinsonNarrower topic: Undecidability places Hilbert’s question among problems no algorithm can solve.

• Theoretical computer scienceBroader topic: It identifies fundamental limits on computation, independent of available resources.

• Automated reasoningRelated: Its limits explain why no reasoning engine can decide every mathematical question.

• Blum's speedup theoremNarrower topic: The theorem separates computability from the possibility of stable resource efficiency.

• Post's theoremNarrower topic: Post's theorem is a foundational bridge within this field.

• S-m-n theoremNarrower topic: The theorem is a foundational tool for reasoning about computable programs and indices.

• Blum axiomsNarrower topic: The axioms rely on computability while adding constraints about resource measurement.

• Model of computationNarrower topic: It examines the limits shared by sufficiently expressive computational models.