Theory of Computation

Pioneers whose defining contribution is one of the foundational questions Theory of Computation studies: what a computation can achieve, how efficiently, and by what formal model, spanning automata theory, computability, computational complexity and, since the 1980s, quantum models of computation. Alonzo Church's lambda calculus and the Church Turing thesis, George Boole's algebra of logic, Stephen Cole Kleene's recursion theory, Claude Shannon's application of Boolean algebra to circuit design, Donald Knuth's analysis of algorithms, Ada Lovelace's 1843 algorithm for the Analytical Engine, Alan Turing's work on computability, David Deutsch's quantum Turing machine and Scott Aaronson's quantum computational complexity research. This group now also holds the atlas's former separate Algorithms and Complexity Theory and Quantum Computing pioneer fields, both branches of the same theoretical question this field already asked. Does not belong here: a pioneer whose defining work is a specific programming language's design or a system's engineering practice rather than a foundational question about computation itself, filed under Software and Its Engineering instead.