(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 E. Black.
Entry modified Fri Feb 27 15:17:39 2004.
HTML page formatted Wed Oct 26 09:47:49 2005.
Cite this as:
Paul E. Black, "model of computation", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/modelOfComputation.html
