For question 2(A), one register can of course only be the predecessor function so you can only go up to $\omega$. For $n$ registers with $n \ge 2$, we have a lower bound ofthe ordinal $\varphi(n-1,0)$ foris the highest ordinal we can reach. Here is how we define We can prove the Value functionslower bound by providing an example of a system of values for $Value_i$ that work up to $\varphi(n-1,0)$, which we will provide next:
In general, $Value_n$ will increment one ordinal after $Value_{n-1}$ resets, so there will be no repeats of $(Value_1,\cdots,Value_n)$ until $Value_n$ resets, by similar reasoning to the above. Given that $Value_{n-1}$ resets at ordinals of the form $\varphi(n-2,\alpha)$, $Value_n$ will increment to $1+\alpha$ at the ordinal $\varphi(n-2,\alpha)+1$, so it will reset at ordinals of the form $\varphi(n-1,\beta)$, and our conclusion follows by induction.
We will now prove that $\varphi(n-1,0)$ is also an upper bound for the highest ordinal we can reach using $n$ registers. We start with the following Theorem:
Definition: We say that register $i$ increments to a limit ordinal $\alpha$ at time $\beta$ if its value at time $\beta$ is defined to be $\alpha$ using rule (4b) (i.e. there is some last time $r$ such that the register $i$ is zero), and $Value_i(\gamma) < \alpha$ for $r < \gamma < \beta$.
Theorem 1. Given an ordinal $\alpha$, when the time is a multiple of $\omega^\alpha$, some register must either increment to a multiple of $\omega^\alpha$, or reset to zero.
Proof: We will use transfinite induction on $\alpha$. For $\alpha = 0$ the theorem statement is trivial.
Next, suppose $\alpha = \beta + 1$, and assume the statement for $\beta$. Suppose that $t = \omega^\alpha s = \omega^\beta (\omega s)$. For each $i$ with $0 < i < \omega s$, at time $\omega^\beta i$ some register will increment to a multiple of $\omega^\beta$ or reset to zero. So we can partition $\omega s$ into $n$ parts depending on which register becomes a multiple. Since $\omega s$ is a limit ordinal and we have finitely many registers, some part must be unbounded, i.e. some register increments to a multiple of $\omega^\beta$ or resets to zero on a set $\omega^\beta S$ with $S$ an unbounded subset of $\omega s$. Now, in this set $\omega^\beta S$ there is either a last time at which register $i$ is zero, or there isn't. In the latter case, register $i$ must reset to zero at time $\omega^\beta (\omega s)$ by rule (4a); in the former case, register $i$ resets to zero at some final time $r$, and beyond that time it can only go up (or stay the same). So the values of register $i$ at times $\omega^\beta S$ beyond $r$ are increasing multiples of $\omega^\beta$, so the value of register $i$ at $\omega^\beta(\omega s)$ must be $\omega^\beta$ times some limit ordinal, i.e. a multiple of $\omega^\alpha$, and register $i$ increments to that multiple of $\omega^\alpha$ at time $\omega^\alpha s$, as desired.
Finally, suppose that $\alpha$ is a limit ordinal, and $t = \omega^\alpha (s+1)$. (If $t$ is $\omega^\alpha$ times some limit ordinal, then simply choose $\alpha$ to be larger.) For each $\beta < \alpha$, at time $\omega^\alpha s + \omega^\beta$ some register must either increment to a multiple of $\omega^\beta$ or reset to zero. Then, either there is no final time before $t$ at which some register resets to zero, or there is not. In the former case, some register must reset to zero at time $t$. In the latter case, there is some final reset time $r$, and some register must increment to a multiple of $\beta$ at time $\omega^\alpha s + \omega^\beta$ for unboundedly many $\beta$ without resetting in between. It follows that the value of that register at time $t$ must be the limit of some increasing sequence $v_\beta$ for $\beta < \alpha$, where $v_\beta$ is a multiple of $\omega^\gamma$ for all $\beta \ge \gamma$. It follows that the limit value $v$ must be a multiple of $\omega^\gamma$ for all $\gamma < \alpha$, implying that it is a multiple of $\omega^\alpha$.
Corollary 1. When the time is of the form $\omega^\alpha$, some register must reset to zero.
Proof: Just apply the previous theorem and observe that there is no multiple of $\omega^\alpha$ less than $\omega^\alpha$ except $0$.
Definition: Let $W_\alpha$ be the class of ordinals that are multiples of $\omega^\alpha$.
Theorem 2. For any positive integer $m$ and ordinal $\alpha$, when the time is of the form $\varphi(m, \beta)$ with $\beta \in W_\alpha$, there will be $m+1$ registers that reset to zero and one other register that either resets to zero or increments to a member of $W_\alpha$.
Proof: We will induct on $m$ and $\alpha$.
Case $m=1$:
- Case $\alpha = 0$: Applying Corollary 1, at times of the form $\omega^\gamma$ some register must reset to 0. So before the time $\varphi(1,\beta)$, some register must reset to 0 at the times $\omega^S$ for some set $S$ unbounded in $\varphi(1,\beta)$; therefore it must reset at time $\varphi(1,\beta)$. Consider the remaining $n-1$ registers. Either one of those registers does not have a final time at which it resets to zero before time $\varphi(1,\beta)$, or there is some final time $r$ beyond which no register ever resets. In the former case that register must reset to zero at time $\varphi(1,\beta)$; in the latter case, at each ordinal of the form $\omega^gamma$ beyond $r$ we must increment some register without ever resetting in between. So by the time $\varphi(1,\beta)$ some register must be incremented $\varphi(1,\beta)$ times without resetting in between, so it must reset at $\varphi(1,\beta)$. Thus at $\varphi(1,\beta)$ at least two registers must reset.
- Case $\alpha = \gamma + 1$: From the previous case, at every time $\varphi(1,\beta)$ two registers must reset. Thus before $\varphi(1,\omega^\alpha s)$ there must be at least one pair of registers which reset at $\varphi(1,\beta)$ for some set $S$ unbounded in $\omega^\alpha s$. So we consider the remaining $n-2$ registers at times of the form $\varphi(1,\beta)$, and the theorem follows by an argument almost identical to the successor case in Theorem 1.
- Case $\alpha$ is limit: proof identical to limit case in Theorem 1.
Now, we will prove the theorem for $m$ assuming the theorem for $m-1$.
- Case $\alpha = 0$: By assumption, for every $\beta$, and for every $\gamma \in W_\beta$, at time $\varphi(m-1,\gamma)$ some collection of $m$ registers will all reset to 0, and some other register that either resets to zero or increments to some element of $W_\beta$. In particular, at the time $\varphi(m,\delta) = \varphi(m-1,\varphi(m,\delta))$, there will be $m$ registers that reset to zero and some other register must either reset to zero or increment to an element of $W_{\varphi(m,\delta)}$. But the smallest nonzero element of $W_{\varphi(m,\delta)}$ is $\varphi(m,\delta)$, so that last register must reset to zero as well, and we have $m$ registers that reset to zero.
- Case $\alpha = \gamma+1$: Identical to previous argument.
- Case $\alpha$ is limit: Identical to previous argument.
QED
In particular, at time $\varphi(n-1,0)$ all $n$ registers must reset to zero, so that is the limit of this system.
