# Theory of computation The theory of computation is the branch of [[Computer_science|computer science]] and [[Discrete_mathematics|discrete mathematics]] that asks three questions with mathematical finality: what can be computed at all, what can be computed efficiently, and what machinery is needed for each answer. Its founding surprise is that these questions have machine-independent answers — an [[Algorithm|algorithm]]'s possibility or impossibility does not depend on the hardware, the [[Computer_programming|programming language]], or the century. Born inside [[Logic|logic]] in the 1930s, before electronic computers existed, the field now polices the boundary every vault discipline eventually hits: [[Cryptography|cryptography]] rests on problems believed hard, [[Combinatorial_optimization|combinatorial optimization]] budgets against NP-hardness, and any [[Complex_system|complex-system]] model faces the fact that some questions about [[Formal_system|formal systems]] admit no answering procedure whatsoever. ## Three questions, three subfields The discipline splits cleanly. *Automata theory* classifies abstract machines by memory discipline: [[Finite-state_machine|finite-state machines]] recognize exactly the regular languages, pushdown automata (a stack added) the context-free ones, and Turing machines — unbounded tape, invented by Alan Turing in 1936 — the full computable class; Chomsky's hierarchy (1956) stacked these into the ladder that still organizes compilers and [[Sequential_logic|sequential logic]]. *Computability theory* asks what any machine on the ladder's top rung can do, and its landmark results are negative. *Complexity theory* (framed by Hartmanis and Stearns, 1965) grades the possible by resource consumption — time, space, randomness — and holds the field's most famous open problem. The three share one method: precise machine models plus [[Deductive_reasoning|deductive]] proof, which is why results from 1936 remain exactly true. ## The Church–Turing thesis and the undecidable Three independent 1936 formalisms — Turing's machines, Church's λ-calculus, Gödel–Kleene recursive functions — turned out to define the same class of functions, and the Church–Turing thesis names the induction: this class *is* effective computability. The thesis buys universality: a single universal machine can simulate any other given its description, the mathematical seed of the stored-program computer and the [[Von_Neumann_architecture|von Neumann architecture]] (1945). It also buys impossibility. Turing's halting problem — decide whether an arbitrary program halts — is undecidable by a diagonal argument descended from Cantor's [[Set_theory|set theory]], and Rice's theorem (1951) extends the verdict to every nontrivial semantic property of programs, which is why perfect [[Correctness_(computer_science)|correctness]] checkers and perfect malware detectors are mathematically, not merely currently, impossible. The [[Self-reference|self-reference]] driving these proofs is the same engine as Gödel's incompleteness theorems (1931) — the [[Strange_loop|strange loop]] at the bottom of [[First-order_logic|first-order]] formal reasoning. ## Complexity: pricing the possible Among solvable problems, cost is destiny. P collects problems solvable in time polynomial in input size; NP collects those whose solutions can be *verified* that fast; and whether P = NP — posed sharply by Cook's theorem (1971), which made Boolean satisfiability the first NP-complete problem, with Karp's 21 reductions (1972) spreading completeness across [[Graph_theory|graph theory]], scheduling, and [[Operations_research|operations research]] — remains the central open question, one of the Clay Millennium Problems (2000). The practical grammar is reduction: prove your scheduling task NP-complete and [[Algorithmic_efficiency|efficiency]] hopes shift to approximation, heuristics like [[Ant_colony_optimization_algorithms|ant colony optimization]], or restricted instances. Randomness joins the resource list — [[Monte_Carlo_method|Monte Carlo]] algorithms trade certainty for speed — and [[Quantum_computing|quantum computing]] genuinely rearranges the map: Shor's algorithm (1994) factors integers in polynomial time, threatening the RSA foundations of [[Cryptography|cryptography]], while Grover's (1996) gives a provable quadratic search speedup and no more. ## Computation in the physical world The theory keeps colliding productively with physics and engineering. [[Claude_Shannon|Claude Shannon]]'s 1937 master's thesis showed [[George_Boole|Boole]]'s 1854 algebra is the calculus of relay circuits, wiring logic into [[Logic_gate|logic gates]]; [[Warren_Sturgis_McCulloch|McCulloch]] and [[Walter_Pitts|Pitts]] (1943) proved nets of threshold neurons equivalent to finite automata, seeding both [[Neural_network_(machine_learning)|neural networks]] and [[Cybernetics|cybernetics]]' conviction that brains compute. Thermodynamics sets a floor: Landauer's principle (1961) prices each erased bit at k_B·T·ln 2 ≈ 3×10⁻²¹ J at room temperature, binding [[Entropy_(information_theory)|information-theoretic entropy]] to physical [[Entropy|entropy]] and making [[Information_theory|information theory]] the field's thermodynamic conscience. And computation appears unbidden in simple dynamics: [[John_von_Neumann|von Neumann]]'s self-reproducing automaton (late 1940s) put [[Self-replication|self-replication]] on rigorous footing, [[Conway's_Game_of_Life|Conway's Game of Life]] (1970) and elementary rule 110 (Cook's proof, published 2004) are Turing-complete [[Cellular_automaton|cellular automata]], and that universality is a standing warning for [[Systems_science|systems science]]: a [[Dynamical_system|dynamical system]] rich enough to compute inherits undecidable long-run questions — [[Emergence|emergence]] with a proof attached. ## What the boundary means for modelers For the vault's systems reader, three portable lessons. First, universality is cheap: astonishingly small rule sets ([[Elementary_cellular_automaton|elementary cellular automata]], tiny [[Recursion_(computer_science)|recursive]] cores) already compute everything computable, so simplicity of rules certifies nothing about simplicity of behavior. Second, verification outruns discovery: NP's whole definition is that checking is easy where finding may not be — a distinction [[Decision_theory|decision theory]] and [[Machine_learning|machine learning]] both inherit, since training is search but auditing is verification. Third, impossibility results are design constraints, not defeats: [[Error_detection_and_correction|error correction]], [[Fault_tolerance|fault tolerance]], and cryptographic protocols are all architectures built *on* proven limits, engineering certainty out of bounded ignorance. The theory of computation, in short, is the vault's supreme court — the place where questions about [[System|systems]] get final answers, including the final answer that some questions never will. **On the spine:** [[Algorithm]] · [[Finite-state_machine]] · [[Information_theory]] · [[Cellular_automaton]] · [[Cybernetics]]. ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Theory_of_computation) : [Wikitube](https://en.wikitube.io/wiki/Theory_of_computation) ## Previous hub tags Hubs: `Systems`. Portals: [[PORTAL_Systems]], [[PORTAL_Information_theory]], [[PORTAL_Systems_science]], [[PORTAL_Cybernetics]], [[PORTAL_Graph_theory]]. --- *Repopulated 2026-08-12 · redlink fill · 0 deletions.*