In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, and more specifically in
computability theory and
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, 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.
The
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
of an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
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
Sequential models include:
*
Finite state machines
* Post machines (
Post–Turing machines and
tag machines).
*
Pushdown automata
*
Register machine
In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. All the models are Turing equivalent.
Overview
The register machine gets its name from ...
s
**
Random-access machines
*
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algor ...
s
*
Decision tree model
Functional models
Functional models include:
*
Abstract rewriting systems
*
Combinatory logic
*
General recursive functions
*
Lambda calculus
Concurrent models
Concurrent models include:
*
Actor model
*
Cellular automaton
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tess ...
*
Interaction nets
*
Kahn process networks
*
Logic gate
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic ga ...
s and
digital circuits
*
Petri nets
*
Synchronous Data Flow
Some of these models have both
deterministic and
nondeterministic
Nondeterminism or nondeterministic may refer to:
Computer science
* Nondeterministic programming
*Nondeterministic algorithm
In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit diffe ...
variants. Nondeterministic models are not useful for practical computation; they are used in the study of
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
of algorithms.
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.
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.
See also
*
Stack machine (0-operand machine)
*
Accumulator machine (1-operand machine)
*
Register machine
In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. All the models are Turing equivalent.
Overview
The register machine gets its name from ...
(2,3,... operand machine)
*
Random-access machine
*
Abstract machine
An abstract machine is a computer science theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is analogous to a mathematical function in that it receives inputs and produces outputs based on p ...
*
Cell-probe model In computer science, the cell-probe model is a model of computation similar to the random-access machine, except that all operations are free except memory access. This model is useful for proving lower bounds of algorithms for data structure probl ...
*
Robertson–Webb query model
*
Chomsky hierarchy
In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars.
This hierarchy of grammars was described ...
*
Turing completeness
References
Further reading
*
*
{{DEFAULTSORT:Model Of Computation
Computational complexity theory
Computability theory