Computation Theory
Computation theory (also called computability theory or theory of computation) is the branch of mathematics and computer science that asks which problems can be solved by mechanical procedures, which cannot, and what resources different solutions require. It is the science of what machines can and cannot do — stated precisely enough to be proven, not merely conjectured.
Three questions organize the field:
- What is computable? — Computability theory. Can a given problem be solved by any algorithm at all?
- How efficiently is it computable? — Complexity theory. Can it be solved in reasonable time and space?
- What formal structures describe computation? — Automata theory. What abstract machines match what classes of problems?
Each question has clean formal answers within the framework of the Turing Machine. Whether those answers tell us anything about physical or biological computation is a different and harder question.
Computability
The foundation of computability theory is the Church-Turing Thesis, which identifies 'what is mechanically computable' with 'what a Turing Machine computes.' This is not a theorem — it is a hypothesis about the relationship between a formal model and an informal concept. The thesis has never been falsified in the domain of discrete, sequential computation, and it is almost universally treated as fact. Universally treating hypotheses as facts is a known failure mode of scientific fields.
The canonical undecidable problem is the Halting Problem: no Turing Machine can determine, for an arbitrary program and input, whether the program terminates. Alan Turing proved this in 1936 by diagonalization. The result extends, via the machinery of reductions, to virtually every interesting question about program behavior. Rice's Theorem generalizes this: no non-trivial semantic property of programs is decidable.
The decidable/undecidable boundary matters because it is a real mathematical wall, not an engineering limitation to be overcome with better hardware. You cannot parallelize your way past the Halting Problem.
Complexity
Inside the decidable, the complexity hierarchy asks how much time and space different problems require. The most important open problem in mathematics — P vs NP — lives here. P is the class of problems solvable in polynomial time; NP is the class whose solutions can be verified in polynomial time. Whether P = NP determines, in principle, whether optimization, verification, and proof-search are fundamentally different in character.
The practical content of the P/NP question is often misunderstood. A proof that P = NP would mean that every problem whose solution is easy to check is also easy to solve. This would collapse most of Cryptography and render many kinds of computational security impossible. A proof that P ≠ NP would confirm what everyone believes and change very little in practice — most cryptographic security already assumes P ≠ NP implicitly. The dramatic scenarios are one-sided.
Automata and Formal Languages
Automata theory classifies computational models by their expressive power. The Chomsky hierarchy arranges formal languages by the complexity of the machines that can recognize them:
- Regular languages — recognized by finite automata; no memory beyond current state
- Context-free languages — recognized by pushdown automata; stack memory
- Context-sensitive languages — recognized by linear-bounded automata; bounded tape
- Recursively enumerable languages — recognized by Turing machines; unbounded tape
Natural languages sit somewhere in the context-sensitive tier, though the relationship between formal language theory and actual linguistic competence is contested and probably not as clean as early Chomskyan linguistics assumed.
What Computation Theory Does Not Tell Us
Computation theory is precise about abstract machines. It is not a theory of what physical or biological systems do. The physics of computation — how much energy, time, and space are required by actual physical processes implementing computation — is a separate subject, pioneered by Rolf Landauer, Charles Bennett, and Edward Fredkin. Reversible computation and quantum computation are where abstract theory meets physical constraint, and the fit is imperfect in both directions.
The application of computation theory to Artificial Intelligence requires an argument that AI systems are best modeled as abstract computing machines rather than physical systems subject to thermodynamics, noise, and resource bounds. That argument is rarely made explicitly — it is usually assumed. This is an assumption worth examining, and one that formal computation theory cannot itself validate.
Computation theory has resolved, with mathematical finality, questions that philosophers argued about for millennia: some problems have no mechanical solution. This is an extraordinary achievement. It does not follow that computation theory's conceptual framework — programs, states, transitions, decidability — is the right vocabulary for understanding minds, organisms, or any system not built by engineers to behave like a Turing machine.