CS ATLAS A map of computing

Domain 02 —

Theory of Computation

5 topics1936 — 1965
1936Turing Machine1936Lambda Calculus1936Computability & the Halting Problem1943Automata & Formal Languages1965Computational Complexity

Chronology — 21 entries

Chronology

Every milestone in this domain, ordered by date. An event shared by several topics is counted once.

1936On Computable NumbersThe Turing machine — and the universal Turing machine — are born.Turing Machine
1936Church introduces the lambda calculusAn equivalent model of computability, built from function abstraction.Turing Machine
1936The halting problem is undecidableThe diagonal argument, applied to programs.Computability & the Halting Problem
1936The Entscheidungsproblem has no solutionHilbert's programme is proved impossible.Computability & the Halting Problem
1940Simply typed lambda calculusChurch adds types to avoid paradoxes.Lambda Calculus
1943The McCulloch–Pitts neuronNeural activity described with logic gates.Automata & Formal Languages
1945von Neumann's EDVAC reportTurns the universal Turing machine into a stored-program architecture.Turing Machine
1950The Turing testPuts an operational definition of intelligence on the table.Turing Machine
1951Kleene's theoremRegular expressions and finite automata are equivalent.Automata & Formal Languages
1953Rice's theoremEvery non-trivial semantic property of programs is undecidable.Computability & the Halting Problem
1956The Chomsky hierarchyFormal languages classified by generative power.Automata & Formal Languages
1958LISP appearsMcCarthy designs it at MIT, bringing the lambda calculus into programming languages.Lambda Calculus
1965LR parsingKnuth defines a grammar class that can be parsed efficiently.Automata & Formal Languages
1965Polynomial time as the yardstickProposed independently by Cobham and Edmonds.Computational Complexity
1969Curry–Howard correspondencePrograms and proofs are shown to be the same kind of object.Lambda Calculus
1970Denotational semanticsScott builds a model of the lambda calculus from domain theory.Lambda Calculus
1970Recursion theory takes shapeComputability becomes a branch of its own.Computability & the Halting Problem
1971Cook's theoremSAT is NP-complete.Computational Complexity
1972Karp's 21 problemsNP-completeness turns out to be everywhere.Computational Complexity
1992The PCP theoremA deep link between approximation and proof verification.Computational Complexity
2000P vs NP becomes a Millennium ProblemA one-million-dollar prize on the table.Computational Complexity

Curriculum

Courses and labs

Which university courses this domain usually maps to, and whether the practical work is a standalone project course or an in-class lab.

Problem sets and proofs, almost no lab

There is almost no lab work. The only programming assignment is usually “write a simulator for an automaton or a Turing machine”.

Courses

Formal Languages and AutomataTheory of Computation / ComputabilityComputational Complexity (graduate)

Open courses

  • MIT 6.045 Automata, Computability and Complexity
  • Berkeley CS 172 Computability and Complexity

What the labs look like

  • Turing machine / DFA simulator

    The one programming task most courses set: implement transitions and run test strings

  • Reduction exercises

    Reducing 3-SAT to independent set and the like — paper work, not lab work