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.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 27 February 2004.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "model of computation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 27 February 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/modelOfComputation.html