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 (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.

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. See McCarthy formalism for more about the conditional expression "IF r=0 THEN z true ELSE z false " ===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 (to accommodate any size integer) but left-ended. These three tapes are called "Post–Turing (i.e. Wang-like) tapes". The individual heads move to the left (for decrementing) and to the right (for incrementing). In a sense, the heads indicate "the top of the stack" of concatenated marks. Or in Minsky (1961) and Hopcroft and Ullman (1979), 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 (1961) and Shepherdson–Sturgis (1963) 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 (or some other uniquely encodable Encodable-decodable 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 (i) multiply the Gödel number by a constant (numbers "2" or "3"), and (ii) divide by a constant (numbers "2" or "3") and jump if the remainder is zero. Minsky (1967) shows that the need for this bizarre instruction set can be relaxed to { INC (r), JZDEC (r, z) } and the convenience instructions { CLR (r), J (r) } if two tapes are available. However, a simple Gödelization is still required. A similar result appears in Elgot–Robinson (1964) with respect to their RASP model. ==See also== Counter machine Counter-machine model Pointer machine Random-access machine Random-access stored-program machine Turing machine Universal Turing machine Turing machine examples Wang B-machine Post–Turing machine - description plus examples One-instruction set computer Algorithm Algorithm characterizations Halting problem Busy beaver Stack machine WDR paper computer ==Notes== ==References== ==Further reading== ==External links== Igblan - Minsky Register Machines

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378824690 under CC BY-SA 4.0; modifications have been made.