Definition:Unlimited Register Machine/Register

From ProofWiki
Jump to navigation Jump to search

Definition

A URM has a sequence of registers which can store natural numbers: $\set {0, 1, 2, \ldots}$.

Any given URM program may make use of only a finite number of these registers.


Registers are usually referred to by the subscripted uppercase letters $R_1, R_2, R_3, \ldots$.

The number held at any one time by a register is usually referred to by the corresponding lowercase letter $r_1, r_2, r_3, \ldots$.


The registers are unlimited in the following two senses:

$(1): \quad$ Although a URM program may make use of only a finite number of registers, there is no actual upper bound on how many a particular URM program can actually use.
$(2): \quad$ There is no upper bound on the size of the natural numbers that may be stored in any register.


Index of Register

The subscript (which is a natural number) appended to a URM register is called the index of that register.

Hence, for example, the index of register $R_5$ is $5$.


Also see

  • Results about unlimited register machines can be found here.


Sources