Category:Unlimited Register Machines

From ProofWiki
Jump to navigation Jump to search

This category contains results about Unlimited Register Machines.
Definitions specific to this category can be found in Definitions/Unlimited Register Machines.

An unlimited register machine, abbreviated URM, is an abstract machine with the following characteristics:


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

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

Registers are usually referred to by the subscripted uppercase letters $R_1, R_2, R_3, \ldots$. The subscript (which is a natural number) is called the index of the register.

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


The numbers held in the registers of a URM are manipulated according to a program.

A URM program is a finite list of basic instructions.

The instructions are written in a fixed order and numbered $1, 2, 3, \ldots$.

For historical reasons, the number of the instruction is called its line number.

We can refer either to the line of the program or the line in the URM.

It is convenient to use $\Bbb U$ to stand for the set of all URM programs.


This category has only the following subcategory.