Register machine


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, and Random-Access Stored-Program Machine, 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:
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:
  1. An unbounded number of labelled, discrete, unbounded registers unbounded in extent : a finite set of registers each considered to be of infinite extent and each holding a single non-negative integer. The registers may do their own arithmetic, or there may be one or more special registers that do the arithmetic. See also Random-access machine.
  2. 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 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" that move "clumps" of objects/marks from register to register in one action.
  3. 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.
  4. #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: Reduced RAM, RASP: Augmented RAM, RASP: Includes all of the reduced instructions as well as:.
  5. #Control: Counter machine models: Optionally include. RAM and RASP models: Most include, or. All models: Include at least one conditional "jump" following the test of a register, such as. All models optionally include:.
  6. #Register-addressing method:
  7. #*Counter machine: no indirect addressing, immediate operands possible in highly atomized models
  8. #*RAM and RASP: indirect addressing available, immediate operands typical
  9. #Input-output: optional in all models
  10. State register: A special Instruction Register, 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 the address specified by the table and temporarily stored in the IR for direct addressing, or 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" of the RASP. 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: the IR, and a PC for the program stored in the registers. Additionally, aside from the PC, a RASP may also dedicate another register to the "Program-Instruction Register".
  11. List of labelled instructions, usually in sequential order: A finite list of instructions. In the case of the counter machine, random-access machine, 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.
  1. *Observe also that the abacus model combines two instructions, JZ then DEC: e.g..
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, Rózsa Péter, and Heinz Kaphengst, the second step with Hao Wang and, as noted above, furthered along by Zdzislaw Alexander Melzak, Joachim Lambek and Marvin Minsky.
The last five names are listed explicitly in that order by Yuri Matiyasevich. He follows up with:
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 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:
To these four both Wang and then C. Y. Lee added another instruction from the Post set, and then a Post's unconditional jump and, Melzak, Shepherdson and Sturgis. Indeed, Shepherdson and Sturgis remark that:
Martin Davis eventually evolved this model into the Post–Turing machine.
Difficulties with the Wang/Post–Turing model:
Except there was a problem: the Wang model was still a single-tape Turing-like device, however nice its sequential program instruction-flow might be. Both Melzak and Shepherdson and Sturgis observed this :
Indeed, as examples in Turing machine examples, Post–Turing machine and partial functions show, the work can be "complicated".

Minsky, Melzak–Lambek and Shepherdson–Sturgis models "cut the tape" into many

Initial thought leads to 'cutting the tape' so that each is infinitely long but left-ended. These three tapes are called "Post–Turing tapes". The individual heads move to the left and to the right. In a sense, the heads indicate "the top of the stack" of concatenated marks. Or in Minsky and Hopcroft and Ullman, the tape is always blank except for a mark at the left end—at no time does a head ever print or erase.
Care must be taken to write the instructions so that a test for zero and a jump occur before decrementing, otherwise the machine will "fall off the end" or "bump against the end"—creating an instance of a partial function.
Minsky and Shepherdson–Sturgis prove that only a few tapes—as few as one—still allow the machine to be Turing equivalent if the data on the tape is represented as a Gödel number ; this number will evolve as the computation proceeds. In the one tape version with Gödel number encoding the counter machine must be able to multiply the Gödel number by a constant, and divide by a constant and jump if the remainder is zero. Minsky shows that the need for this bizarre instruction set can be relaxed to and the convenience instructions if two tapes are available. However, a simple Gödelization is still required. A similar result appears in Elgot–Robinson with respect to their RASP model.