Definition:Unlimited Register Machine/Program/Highest Register
Jump to navigation
Jump to search
Definition
Let $\Bbb U$ denote the set of all URM programs.
Let $P \in \Bbb U$ be a URM program.
By definition, $P$ uses a finite number of registers.
We define the function $\rho: \Bbb U \to \N$ as follows:
- $\forall P \in \Bbb U: \map \rho P =$ the highest register number used by $P$
That is, in any URM program $P$, no instruction refers to any register with index greater than $\map \rho 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)