(definition)
Definition: A formal, abstract definition of a computer. Using a model one can more easily analyze the intrinsic execution time or memory space of an algorithm while ignoring many implementation issues. There are many models of computation which differ in computing power (that is, some models can perform computations impossible for other models) and the cost of various operations.
Specialization (... is a kind of me.)
Turing machine, random access machine, primitive recursive, cellular automaton, finite state machine, cell probe model, pointer machine, alternation, alternating Turing machine, nondeterministic Turing machine, oracle Turing machine, probabilistic Turing machine, universal Turing machine, quantum computation, parallel models: multiprocessor model, work-depth model, parallel random-access machine, shared memory.
See also big-O notation.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 27 February 2004.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "model of computation", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 27 February 2004. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/modelOfComputation.html