Overview
Computability Theory (also known as Recursion Theory) studies what can and cannot be computed by a machine (algorithm). It defines the absolute limits of computation.
Core Idea
The core idea is that some problems are unsolvable. No matter how powerful computers become, there are specific mathematical questions that no algorithm can ever answer.
Formal Definition
The theory is built on formal models of computation, primarily the Turing Machine. A function is “computable” if there exists a Turing Machine that can calculate it.
Intuition
Imagine a computer with infinite memory and infinite time. Computability theory asks: “Is there anything this super-computer still can’t do?” The answer is yes.
Examples
- The Halting Problem: Can we write a program that takes any other program as input and decides whether it will eventually stop or run forever? Turing proved No. This is undecidable.
- Entscheidungsproblem: Hilbert asked for an algorithm to decide the validity of any logical statement. Turing and Church proved no such algorithm exists.
Common Misconceptions
- Misconception: “Uncomputable” just means “really hard to compute.”
- Correction: No. It means impossible to compute. Complexity Theory deals with “hard” (P vs NP); Computability Theory deals with “impossible.”
- Misconception: Humans can solve things computers can’t.
- Correction: The Church-Turing Thesis suggests that anything computable by any physical process (including the brain) is computable by a Turing Machine.
Related Concepts
- Turing Machine: A mathematical model of computation that defines an abstract machine.
- Complexity Theory: Studies the resources (time/space) required to solve computable problems.
- Gödel’s Incompleteness Theorems: Closely related to undecidability.
Applications
- Compiler Design: Understanding that you can’t write a compiler that perfectly optimizes code or detects all bugs (because of the Halting Problem).
- Mathematics: Proving that certain equations (Diophantine equations) have no algorithmic solution (Matiyasevich’s Theorem).
Criticism and Limitations
- Hypercomputation: Some theoretical models propose machines stronger than Turing Machines, but none have been physically realized.
Further Reading
- Computability and Logic by George Boolos et al.
- The Annotated Turing by Charles Petzold