Which problems can be solved by a computer at all, regardless of how long it takes?
Computability theory (also called recursion theory) deals with the question of whether a problem is solvable on a computer. It determines the boundaries of what algorithms can achieve.
The field builds on fundamental results:
- Halting problem - cannot be solved by any algorithm
- Rice’s theorem - all non-trivial properties of partial functions are undecidable
- Uses Turing machines as the primary model
Computability theory is closely related to mathematical logic’s recursion theory, which removes the restriction of studying only models reducible to Turing machines.
- Studies which problems are solvable
- Uses Turing machine as standard model
- Major result: halting problem is undecidable
- Builds on the halting problem result
- Often synonymous with recursion theory
- Built from: Turing Machine, Halting Problem, Rice's Theorem
- Builds into: Computational Complexity Theory
- Related: Mathematical Logic, Recursion Theory, Model of Computation
- “Undecidable” means no algorithm exists—not just that no one has found one
- Some problems are undecidable even though individual instances may be solvable
Computability theory defines the fundamental limits of what computers can do. Knowing a problem is undecidable saves time trying to find a solution that doesn’t exist.