Theory of Computation

The P versus NP Problem

Stephen Cook

States the problem as one of the seven Millennium Prize Problems and surveys why most computer scientists suspect, but cannot yet prove, that P and NP are different classes.

The Status of the P Versus NP Problem

Lance Fortnow

Surveys decades of attempts to resolve whether P equals NP, arguing that every known proof technique faces a formal barrier explaining why the question has resisted settlement.

The Busy Beaver Frontier

Scott Aaronson

Surveys sixty years of the busy beaver function, arguing that pinning down each new value amounts to resolving a real open mathematical conjecture, since the function inherits its uncomputability directly from the halting problem.

A Mathematical Theory of Communication

Claude Shannon

Defines information quantitatively and proves the limits of compression and error-free transmission over noisy channels.

Assumes probability and logarithms, plus the patience to let the opening pages define everything they use

Finite Combinatory Processes - Formulation 1

Emil L. Post

Sets out an alternative, independently discovered model of mechanical computation built from a worker following fixed instructions along a symbol space, arriving at the same notion of computability as Turing's machine and Church's lambda calculus.

Recursively Enumerable Sets of Positive Integers and Their Decision Problems

Emil L. Post

Surveys recursively enumerable sets as the natural class for undecidable problems, and poses Post's problem asking whether any such set has intermediate computational difficulty between decidable and maximally hard.

Classes of Recursively Enumerable Sets and Their Decision Problems

H. G. Rice

Proves that every non-trivial semantic property of a program's behaviour is undecidable, generalising the halting problem to all such questions about programs at once.

Three Models for the Description of Language

Noam Chomsky

Compares finite-state, phrase-structure and transformational grammars as models of language, arguing finite-state Markov models cannot capture the structure of natural language.

Finite Automata and Their Decision Problems

Michael O. Rabin & Dana Scott

Introduces nondeterministic finite automata and proves they recognise exactly the same languages as deterministic ones, while showing several decision problems about automata are algorithmically solvable.

On the Computational Complexity of Algorithms

Juris Hartmanis & Richard E. Stearns

Introduces time complexity as a formal measure of an algorithm's resource use and proves a hierarchy theorem showing that strictly more problems become solvable as the time bound grows, founding computational complexity theory.

On the Length of Programs for Computing Finite Binary Sequences

Gregory J. Chaitin

Defines the complexity of a finite string as the length of the shortest program that produces it, and shows most strings are incompressible, giving algorithmic information theory its founding measure.

Relationships Between Nondeterministic and Deterministic Tape Complexities

Walter J. Savitch

Proves that any problem solvable by a nondeterministic Turing machine using S(n) space can be solved deterministically in roughly S(n)-squared space, showing nondeterminism costs far less for space than it does for time.