Computability and Decidability
Computability theory studies the fundamental limits of algorithmic problem solving, marking the boundary between problems that can be solved by some effective procedure and those that no algorithm can ever decide.
Definition
Computability theory is the study of which functions and decision problems are computable by an effective procedure; a problem is decidable if some algorithm always halts with the correct yes-or-no answer, and undecidable if no such algorithm exists.
Scope
This area covers formal models of effective computation such as Turing machines, the Church–Turing thesis identifying these models with the intuitive notion of algorithm, the existence of undecidable problems including the halting problem, reductions used to transfer unsolvability between problems, and the structure of degrees of unsolvability that classify problems beyond the computable.
Sub-topics
Core questions
- What does it mean for a problem to be solvable by an algorithm?
- Are there well-defined problems that no algorithm can ever solve?
- How can the unsolvability of one problem be used to prove the unsolvability of another?
- How are unsolvable problems classified by their relative difficulty?
Key theories
- Turing's model of computation
- Turing's abstract machine formalized the notion of an effective procedure and was used to prove that the halting and decision problems for first-order logic are unsolvable, establishing inherent limits on computation.
- Existence of undecidable problems
- By a diagonal argument there are problems, most famously the halting problem, that no algorithm can decide, so undecidability is a pervasive structural feature rather than a curiosity.
- Equivalence of computation models
- Turing machines, the lambda calculus, and recursive functions define exactly the same class of computable functions, the convergence that underwrites the Church–Turing thesis.
Clinical relevance
Undecidability results set hard limits on what software tools can guarantee: no general algorithm can decide whether an arbitrary program halts, is correct, or is free of certain bugs, which is why verification tools rely on approximation, restricted languages, and human guidance rather than complete automatic analysis.
History
Prompted by Hilbert's Entscheidungsproblem, Church and Turing independently showed in 1936 that no algorithm can decide all of first-order logic, with Turing's machine model and Church's lambda calculus proving equivalent. Post and Kleene extended the theory into the study of degrees of unsolvability in the following decades.
Key figures
- Alan Turing
- Alonzo Church
- Kurt Gödel
- Emil Post
Related topics
Seminal works
- turing1937
- church1936
- sipser2013
Frequently asked questions
- What is the difference between decidable and undecidable?
- A problem is decidable if there is an algorithm that always halts and gives the correct yes-or-no answer for every input. It is undecidable if no such algorithm can exist, as proven for the halting problem; an undecidable problem may still be recognizable, meaning an algorithm can confirm yes-instances but might run forever on no-instances.
- Does undecidability mean these problems can never be tackled?
- It means no single algorithm solves every instance correctly. In practice tools handle restricted cases, give approximate or conservative answers, or solve many instances while occasionally failing or asking for help, so undecidability shapes how problems are attacked rather than forbidding all progress.