# Models of computation: Summaries

* Turing machine (TM), 1930s, Alan Turing
* Lambda Calculus (LC), 1930s, Alonzo Church
* Primitive Recursive Function (PRF), Kurt Gödel
* General Recursive Function (GRF), Kurt Gödel

1. *Sequential models* Turing machines Register machines Finite state machines Post machines (Post-Turing machines and tag machines) Pushdown automata Random-access machines
2. *Functional models* Lambda calculus Combinatory logic Abstract rewriting systems General recursive functions μ-recursive functions
3. *Concurrent models* Actor model Cellular automaton Interaction nets Kahn process networks Logic gates and digital circuits Petri nets Synchronous Data Flow

Stack machine (0-operand machine) Accumulator machine (1-operand machine) Register machine (2,3,... operand machine) Random-access machine Cell-probe model Robertson-Webb query model

Chomsky hierarchy Turing completeness

Abstract machine and models equivalent to it (e.g. lambda calculus is equivalent to the Turing machine) - used in proofs of computability and upper bounds on computational complexity of algorithms. Decision tree models - used in proofs of lower bounds on computational complexity of algorithmic problems.

***

Many models of computation have been proposed (all have a notion of discrete time steps, as does a Turing Machine)

1. *Turing Machine* was proposed by Alan Turing in 1936
2. *λ-calculus* was proposed by Alonzo Church in 1941. The λ-calculus enables one to speak of functions from sets of functions to sets of functions
3. *Post systems* were proposed by Emil Post in 1943 They are a generalization of Grammars
4. *Wang machines* were proposed by Hao Wang in 1957
5. *Markov Algorithms* were proposed by Andrei Andreivich Markov in the 1940's
6. *Register machines* were proposed by Abraham Robinson and Calvin Elgot in the 1960's. They resemble an actual computer more than most models.
7. *Random Access Machines* were proposed by Steven Cook and Robert Rechow in the 1970's. They resemble an actual computer more than most models.

Models of computation

* 1936 TM by Alan Turing
* 1941 λ-calculus by Alonzo Church
* 1943 Post system by Emil Post
* 1940's Markov algorithms by Andrei Andreivich Markov
* 1957 Wang machine by Hao Wang
* 1960's Register machines by Abraham Robinson and Calvin Elgot
* 1970's Random Access Machines by Steven Cook and Robert Rechow