In mathematical logic and theoretical computer science, a register machine is a generic class of abstract machines, analogous to a Turing machine and thus Turing complete. Unlike a Turing machine that uses a tape and head, a register machine utilizes multiple uniquely addressed registers to store non-negative integers. There are several sub-classes of register machines, including counter machines, pointer machines, random-access machines (RAM), and random-access stored-program machine (RASP), each varying in complexity. These machines, particularly in theoretical studies, help in understanding computational processes. The concept of register machines can also be applied to virtual machines in practical computer science, for educational purposes and reducing dependency on specific hardware architectures.

Overview

The register machine gets its name from its use of one or more "registers". In contrast to the tape and head used by a Turing machine, the model uses multiple uniquely addressed registers, each of which holds a single non-negative integer.

There are at least four sub-classes found in the literature. In ascending order of complexity:

  • Counter machine – the most primitive and reduced theoretical model of computer hardware. This machine lacks indirect addressing, and instructions are in the finite state machine in the manner of the Harvard architecture.
  • Pointer machine – a blend of the counter machine and RAM models which is less common and more abstract than either model. Instructions are in the finite state machine in the manner of Harvard architecture.
  • Random-access machine (RAM) – a counter machine with indirect addressing and, usually, an augmented instruction set. Instructions are in the finite state machine in the manner of the Harvard architecture.
  • Random-access stored-program machine model (RASP) – a RAM with instructions in its registers analogous to the universal Turing machine, making it an example of the von Neumann architecture. But unlike a computer, the model is idealized with effectively infinite registers (and if used, effectively infinite special registers such as accumulators). As compared to a modern computer, however, the instruction set is still reduced in number and complexity.

Any properly defined register machine model is Turing complete. Computational speed is very dependent on the model specifics.

In practical computer science, a related concept known as a virtual machine is occasionally employed to reduce reliance on underlying machine architectures. These virtual machines are also utilized in educational settings. In textbooks, the term "register machine" is sometimes used interchangeably to describe a virtual machine.

References

</references>

Further reading

  • Igblan - Minsky Register Machines