Definition:Unlimited Register Machine/Program/Length

Definition

Let $\Bbb U$ denote the set of all URM programs.

Let $P \in \Bbb U$ be a URM program.

By definition, $P$ is a finite sequence of basic instructions.

We define the function $\lambda: \Bbb U \to \N$ as follows:

$\forall P \in \Bbb U: \map \lambda P = $ the number of basic instructions that comprise $P$

Thus $\map \lambda P$ is referred to as the length of $P$.

Also see

• Results about unlimited register machines can be found here.

Sources

• 1963: John C. Shepherdson and H.E. Sturgis: Computability of Recursive Functions (J. ACM Vol. 10, no. 2: pp. 217 – 255)

• 1980: N.J. Cutland: Computability: An Introduction to Recursive Function Theory