Page 63 - Textos de Matemática Vol. 38

ORDINALS, COMPUTATIONS, AND MODELS OF SET THEORY 55
iii. if II(t) is the transfer instruction T (m, n) then let I(t + 1) = I(t) + 1 and define R(t + 1) : ω → Ord by
Rk(t+1)= Rm(t), ifk=n, Rk(t), if k ̸= n;
iv. if II(t) is the jump instruction J(m, n, q) then let R(t + 1) = R(t) and I(t+1)= q, if Rm(t)=Rn(t),
I(t) + 1, if Rm(t) ̸= Rn(t);
e) If t < θ is a limit ordinal, the machine constellation at t is determined by
taking inferior limits:
∀k∈ωRk(t) = liminfRk(r); r→t
I(t) = lim inf I(r). r→t
The computation is obviously determined recursively by the initial register con- tents R(0) and the program P. We call it the ordinal computation by P with input R(0). If the computation stops, θ = β + 1 is a successor ordinal and R(β) is the final register content. In this case we say that P computes R(β)(0) from R(0) and write P : R(0) → R(β)(0).
The definition of I(t) for limit t can be motivated as follows. Since a pro- gram is finite its execution will lead to some (complex) looping structure in- volving loops, subloops and so forth. This can be presented by pseudo code like:
...
−→ 17:begin loop
...
21: begin subloop
...
29: end subloop
...
32:end loop
...
Assume that for times r → t the loop (17 − 32) with its subloop (21 − 29) is traversed cofinally often. Then at time t it is natural to put the machine at the start of the “main loop”. Assuming that the lines of the program are enumerated in increasing order this corresponds to the lim inf rule
I(t) = lim inf S(r). r→t
The interpretation of programs yields associated notions of computability.