Page 59 - Textos de Matemática Vol. 38

ORDINALS, COMPUTATIONS, AND MODELS OF SET THEORY 51
3.1 Unlimited register machines - URMs
Definition 3.1. An unlimited register machine URM has registers R0, R1, . . . which can hold natural numbers. A register program consists of commands to increase or to reset a register. The program may jump on condition of equality between two registers.
An URM program is a finite list P = I0, I1, . . . , Is−1 of instructions each of which may be of one of four kinds:
a) the zero instruction Z(n) changes the contents of Rn to 0, leaving all other registers unaltered;
b) the successor instruction S(n) increases the natural number contained in Rn by 1, leaving all other registers unaltered;
c) the transfer instruction T(m,n) replaces the contents of Rn by the natural number contained in Rm, leaving all other registers unaltered;
d) the jump instruction J(m,n,q) is carried out within the program P as fol- lows: the contents rm and rn of the registers Rm and Rn are compared, but all the registers are left unaltered; then, if Rm = Rn, the URM proceeds to the qth instruction of P; if Rm ̸= Rn, the URM proceeds to the next instruction in P.
The instructions of a register program can be addressed by their indices which are called program states. At each ordinal time t the machine will be in a con- figuration consisting of a program state I(t) ∈ ω and the register contents which can be viewed as a function R(t) : ω → ω. R(t)(n) is the content of the register Rn at time t. We also write Rn(t) instead of R(t)(n).
Definition 3.2. Let P = I0,I1,...,Is−1 be a program. A pair I : θ → ω,R : θ → (ωω)
is a (register) computation by P if the following hold:
a) θ ω; θ is the length of the computation;
b) I(0) = 0; the machine starts in state 0;
c) Ift<θandI(t)̸∈s={0,1,...,s−1}thenθ=t+1;themachinestopsif the machine state is not a program state of P;
d) If t < θ and I(t) ∈ state(P) then t+1 < θ; the next configuration is determined by the instruction II(t) :
i. if II(t) is the zero instruction Z(n) then let I(t+1) = I(t)+1 and define R(t + 1) : ω → Ord by
Rk(t+1)= 0, ifk=n, Rk(t), if k ̸= n;