# Model of computation

*https://en.wikipedia.org/wiki/Model_of_computation*

This article relies largely or entirely on a
single source. (February 2021) |

In
computer science, and more specifically in
computability theory and
computational complexity theory, a **model of computation** is a model which describes how an output of a
mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized.^{
[1]} The
computational complexity of an
algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular
implementations and specific technology.

## Models

Models of computation can be classified into three categories: sequential models, functional models, and concurrent models.

Sequential models include:

Functional models include:

Concurrent models include:

- Cellular automaton
- Logic gates and digital circuits
- Kahn process networks
- Petri nets
- Synchronous Data Flow
- Interaction nets
- Actor model

Models differ in their expressive power; for example, each function that can be computed by a *Finite state machine* can also be computed by a *Turing machine*, but not vice versa.

A nondeterministic model of computation is associated with some of these models of computation. Nondeterministic models are not useful for practical computation; they are used in the study of computational complexity of algorithms.

## Uses

In the field of runtime
analysis of algorithms, it is common to specify a computational model in terms of *primitive operations* allowed which have unit cost, or simply **unit-cost operations**. A commonly used example is the
random-access machine, which has unit cost for read and write access to all of its memory cells. In this respect, it differs from the above-mentioned Turing machine model.

## Categories

There are many models of computation, differing in the set of admissible operations and their computations cost. They fall into the following broad categories:

- 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.

## See also

- 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

## References

**^**"Models of Computation" (PDF).

## Further reading

- Fernández, Maribel (2009).
*Models of Computation: An Introduction to Computability Theory*. Undergraduate Topics in Computer Science. Springer. ISBN 978-1-84882-433-1. -
Savage, John E. (1998).
*Models Of Computation: Exploring the Power of Computing*. Addison-Wesley. ISBN 978-0201895391.