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

Previous640-models-of-computationNextModel of computation

Last updated