Definition: A model of computation whose memory consists of an unbounded collection of registers, or records, connected by pointers. Each register may contain an arbitrary amount of additional information. No arithmetic is allowed to compute the address of a register. The only way to access a register is by following pointers.
See also cell probe model, random access machine, Turing machine, big-O notation.
Note: From Algorithms and Theory of Computation Handbook, page 5-25, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 17 December 2004.
HTML page formatted Mon Nov 18 10:44:10 2013.
Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "pointer machine", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/pointermachn.html