 | This articlerelies largely or entirely on asingle source. Relevant discussion may be found on thetalk page. Please helpimprove this article byintroducing citations to additional sources. Find sources: "Model of computation" – news ·newspapers ·books ·scholar ·JSTOR(February 2021) |
Incomputer science, and more specifically incomputability theory andcomputational complexity theory, amodel of computation is a model that describes how an output of amathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized.[1] Thecomputational complexity of analgorithm 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 particularimplementations and specific technology.
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:
Some of these models have bothdeterministic andnondeterministic variants. Nondeterministic models are used in the study ofcomputational complexity of algorithms.
Models differ in their expressive power; for example, each function that can be computed by afinite-state machine can also be computed by aTuring machine, but not vice versa.
In the field of runtimeanalysis of algorithms, it is common to specify a computational model in terms ofprimitive operations allowed which have unit cost, or simplyunit-cost operations. A commonly used example is therandom-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.
