Register Machine


An idealized computing machine consisting of a fixed set of data registers and set of instructions for operating on them. Register machines are also known as counter machines and program machines. Early investigators included Shepherdson and Sturgis (1963) and Minsky (1961). Somewhat similar constructs were also part of Kurt Gödel's 1931 work on representing logic within arithmetic (Wolfram 2002, p. 896).

Wolfram (2002) considers machines with two registers and two operations: "increments" and "decrement-jumps." The above illustration shows 30 steps of a five-instruction program that generate nonrepetitive output (Wolfram 2002, p. 99).

See also

Turing Machine

Explore with Wolfram|Alpha


Minsky, M. L. "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines." Ann. Math. 74, 437-455, 1961.Shepherdson, J. C. and Sturgis, H. E. "Computability of Recursive Functions." J. Assoc. Comput. Mach. 10, 217-255, 1963.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 97-102 and 896, 2002.

Referenced on Wolfram|Alpha

Register Machine

Cite this as:

Weisstein, Eric W. "Register Machine." From MathWorld--A Wolfram Web Resource.

Subject classifications