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.
Formal definition A register machine consists of:
An unbounded number of labelled, discrete, unbounded registers unbounded in extent (capacity): a finite (or infinite in some models) set of registers each considered to be of infinite extent and each holding a single non-negative integer (0, 1, 2, ...). The registers may do their own arithmetic, or there may be one or more special registers that do the arithmetic (e.g. an "accumulator" and/or "address register"). See also Random-access machine. Tally counters or marks: discrete, indistinguishable objects or marks of only one sort suitable for the model. In the most-reduced counter machine model, per each arithmetic operation only one object/mark is either added to or removed from its location/tape. In some counter machine models (e.g. Melzak, Minsky) and most RAM and RASP models more than one object/mark can be added or removed in one operation with "addition" and usually "subtraction"; sometimes with "multiplication" and/or "division". Some models have control operations such as "copy" (or alternatively: "move", "load", "store") that move "clumps" of objects/marks from register to register in one action. A limited set of instructions: the instructions tend to divide into two classes: arithmetic and control. The instructions are drawn from the two classes to form "instruction sets", such that an instruction set must allow the model to be Turing equivalent (it must be able to compute any partial recursive function). Arithmetic: Arithmetic instructions may operate on all registers or on a specific register, such as an accumulator. Typically, they are selected from the following sets, though exceptions exist: Counter machine: { Increment (r), Decrement (r), Clear-to-zero (r) } Reduced RAM, RASP: { Increment (r), Decrement (r), Clear-to-zero (r), Load-immediate-constant k, Add (), Proper-Subtract (), Increment accumulator, Decrement accumulator, Clear accumulator, Add the contents of register to the accumulator, Proper-Subtract the contents of register from the accumulator } Augmented RAM, RASP: Includes all of the reduced instructions as well as: { Multiply, Divide, various Boolean bit-wise operations (left-shift, bit test, etc.) }. Control: Counter machine models: Optionally include { Copy () }. RAM and RASP models: Most include { Copy () }, or { Load Accumulator from , Store accumulator into , Load Accumulator with an immediate constant }. All models: Include at least one conditional "jump" (branch, goto) following the test of a register, such as { Jump-if-zero, Jump-if-not-zero (i.e., Jump-if-positive), Jump-if-equal, Jump-if-not-equal }. All models optionally include: { unconditional program jump (goto) }. Register-addressing method: Counter machine: no indirect addressing, immediate operands possible in highly atomized models RAM and RASP: indirect addressing available, immediate operands typical Input-output: optional in all models State register: A special instruction register (IR), distinct from the registers mentioned earlier, stores the current instruction to be executed along with its address in the instruction table. This register, along with its associated table, is located within the finite state machine. The IR is inaccessible in all models. In the case of RAM and RASP, for determining the "address" of a register, the model can choose either (i) the address specified by the table and temporarily stored in the IR for direct addressing, or (ii) the contents of the register specified by the instruction in the IR for indirect addressing. It's important to note that the IR is not the "program counter" (PC) of the RASP (or conventional computer). The PC is merely another register akin to an accumulator but specifically reserved for holding the number of the RASP's current register-based instruction. Thus, a RASP possesses two "instruction/program" registers: (i) the IR (finite state machine's instruction register), and (ii) a PC (program counter) for the program stored in the registers. Additionally, aside from the PC, a RASP may also dedicate another register to the "program-instruction register" (referred to by various names such as "PIR," "IR," "PR," etc.). List of labelled instructions, usually in sequential order: A finite list of instructions . In the case of the counter machine, random-access machine (RAM), and pointer machine, the instruction store is in the "TABLE" of the finite state machine, thus these models are examples of the Harvard architecture. In the case of the RASP, the program store is in the registers, thus this is an example of the von Neumann architecture. See also Random-access machine and Random-access stored-program machine.The instructions are usually listed in sequential order, like computer programs, unless a jump is successful. In this case, the default sequence continues in numerical order. An exception to this is the abacus counter machine models—every instruction has at least one "next" instruction identifier "z", and the conditional branch has two. Observe also that the abacus model combines two instructions, JZ then DEC: e.g. { INC ( r, z ), JZDEC ( r, ztrue, zfalse ) }. See McCarthy formalism for more about the conditional expression "IF r=0 THEN ztrue ELSE zfalse"
Historical development of the register machine model Two trends appeared in the early 1950s. The first was to characterize the computer as a Turing machine. The second was to define computer-like models—models with sequential instruction sequences and conditional jumps—with the power of a Turing machine, a so-called Turing equivalence. Need for this work was carried out in the context of two "hard" problems: the unsolvable word problem posed by Emil Post—his problem of "tag"—and the very "hard" problem of Hilbert's problems—the 10th question around Diophantine equations. Researchers were questing for Turing-equivalent models that were less "logical" in nature and more "arithmetic."
The first step towards characterizing computers originated with Hans Hermes (1954), Rózsa Péter (1958), and Heinz Kaphengst (1959), the second step with Hao Wang (1954, 1957) and, as noted above, furthered along by Zdzislaw Alexander Melzak (1961), Joachim Lambek (1961) and Marvin Minsky (1961, 1967).
The last five names are listed explicitly in that order by Yuri Matiyasevich. He follows up with: "Register machines [some authors use "register machine" synonymous with "counter-machine"] are particularly suitable for constructing Diophantine equations. Like Turing machines, they have very primitive instructions and, in addition, they deal with numbers".
Lambek, Melzak, Minsky, Shepherdson and Sturgis independently discovered the same idea at the same time. See note on precedence below.
The history begins with Wang's model.
Wang's (1954, 1957) model: Post–Turing machine Wang's work followed from Emil Post's (1936) paper and led Wang to his definition of his Wang B-machine—a two-symbol Post–Turing machine computation model with only four atomic instructions: { LEFT, RIGHT, PRINT, JUMP_if_marked_to_instruction_z } To these four both Wang (1954, 1957) and then C. Y. Lee (1961) added another instruction from the Post set { ERASE }, and then a Post's unconditional jump { JUMP_to_ instruction_z } (or to make things easier, the conditional jump JUMP_IF_blank_to_instruction_z, or both. Lee named this a "W-machine" model: { LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [maybe JUMP or JUMP_IF_blank] } Wang expressed hope that his model would be "a rapprochement" between the theory of Turing machines and the practical world of the computer.
Wang's work was highly influential. We find him referenced by Minsky (1961) and (1967), Melzak (1961), Shepherdson and Sturgis (1963). Indeed, Shepherdson and Sturgis (1963) remark that: "...we have tried to carry a step further the 'rapprochement' between the practical and theoretical aspects of computation suggested by Wang,"
Martin Davis eventually evolved this model into the (2-symbol) Post–Turing machine.
Difficulties with the Wang/Post–Turing model:
Except there was a problem: the Wang model (the six instructions of the 7-instruction Post–Turing machine) was still a single-tape Turing-like device, however nice its sequential program instruction-flow might be. Both Melzak (1961) and Shepherdson and Sturgis (1963) observed this (in the context of certain proofs and investigations):
"...a Turing machine has a certain opacity... a Turing machine is slow in (hypothetical) operation and, usually, complicated. This makes it rather hard to design it, and even harder to investigate such matters as time or storage optimization or a comparison between the efficiency of two algorithms. "...although not difficult... proofs are complicated and tedious to follow for two reasons: (1) A Turing machine has only a head so that one is obliged to break down the computation into very small steps of operations on a single digit. (2) It has only one tape so that one has to go to some trouble to find the number one wishes to work on and keep it separate from other numbers"
Indeed, as examples in Turing machine examples, Post–Turing machine and partial functions show, the work can be "complicated".