Finite Number of Registers and Computable Well-Orderings

Question

I have added the formal definition of the function $address$. The question is divided in two parts. This is important because of two reasons. First due to the length of the question. Secondly if one gives a negative example for the first part, the second part is redundant in that case. I asked the first part of this question on Math.SE (https://math.stackexchange.com/questions/2396322/finite-registers-and-computable-well-orderings-for-omega). I was hoping that if someone would describe a negative example for the first part (which I might have failed to see for any reason), then there wouldn't be any need to post this particular question.

Also finally, even the question in second part is (quite likely) not as general as the title seems to suggest. Here is the question:

First Part

Suppose we are given some computable well-ordering on $\Bbb{N}$ whose order-type is $\omega$. It is assumed that the (total) notation function induced corresponding to the computable well-order relation is denoted as $address:\omega\rightarrow \Bbb{N}$, which is going to be bijective.

Given a computable well-ordering $\preceq$ on $\Bbb{N}$ of order-type $\alpha$, $address$ is meant to be the unique order-preserving bijection from $\alpha$ to $(\Bbb{N},\preceq)$. Thanks to Deedlit for suggesting this precise/formal defintion. My own informal desciption is under EDIT2.

Now suppose we are given two registers (generalising to more than two registers is self-evident). The values of registers are given by the functions $Value_1:\omega\rightarrow\omega$ and $Value_2:\omega\rightarrow\omega$. More specifically, the value of register-1 at some time $t\in\omega$ is denoted by $Value_1(t)$ (and of course same for the other register).

Before stating this question we need to define the representation of a function in a given well-ordering. Now suppose for some computable well-ordering of an element $p$ we are given the notation function $address:p\rightarrow \Bbb{N}$. For some function $F:p \rightarrow p$ we can write representation function of $F$ (in the given well-ordering for $p$) as $f:\Bbb{N} \rightarrow \Bbb{N}$ and defined by: $$f(address(x))=address(F(x)) \qquad for \; all \; x\in p$$

In general we might have to worry about extra cases (in defining representation of the function $F$), but here we won't (since $F$ is total and $F(x)<p$ for all values in the domain). One can also observe that since we are only concerned with case of $\omega$ here, we can replace $p$ with $\omega$ in the preceding paragraph.

And with this, we are pretty much set to ask the question. We just need to define the rules/constraints for how the register values can change. They are:

(1) We must have: $$Value_1(0)=0$$ $$Value_1(1)=0$$ And similarly for second register.

(2) If we have: $$Value_1(t)=a$$

Then only one of the following possibilities can hold at $t+1$:

(a) $Value_1(t+1)=a$ (value remains unchanged)

(b) $Value_1(t+1)=a+1$ (value increased by $1$)

(c) $Value_1(t+1)=0$ (value brought down to $0$)

And obviously the same rule holds for the second register.

(3) There must not exist two different times $t_1$ and $t_2$ at which "all" the register values repeat themselves (simultaneously that is). For two registers, we must not have two different times $t_1$ and $t_2$ (with $t_1\ne 0$ and $t_2\ne 0$) such that: $$Value_1(t_1)=Value_1(t_2)$$ AND $$Value_2(t_1)=Value_2(t_2)$$

Now the question asks that can one find a negative example with a computable well-ordering for $\omega$ such that:

(1) The representation functions corresponding to the functions $Value_1$ and $Value_2$ are recursive in the well-ordering. Note that the functions $Value_1$ and $Value_2$ are entirely arbitrary (apart from the stipulation that they have to satisfy the three constraints mentioned above). Suppose we denote the representation functions (in the given well-ordering) corresponding to $Value_1$ and $Value_2$ as $value_1:\Bbb{N} \rightarrow \Bbb{N}$ and $value_2:\Bbb{N} \rightarrow \Bbb{N}$. This condition just requires that the functions $value_1$ and $value_2$ must be recursive.

(2) The representation function corresponding to the successor function is not recursive in the well-ordering (in a more colloquial manner we could say that the successor function is not recursive in the well-ordering).

In the case a negative example exists that example can simply be described (and the second part of the question is redundant in that case). In case a negative example doesn't exist, the proof can be given (also generalisation to more than two resgisters would be nice of course).

Second Part

In this case the value function (for the i-th register) will generally be $Value_i:p\rightarrow p$ (instead of $Value_i:\omega\rightarrow\omega$). That's because now we are dealing with some computable well-ordering on $\Bbb{N}$ whose order-type is $p$ (where $p>\omega$). Other than that, on top of three rules for register values described in first part, we need to describe how we want to evaluate the register value for some limit ordinal (say $q$). So we need to add a fourth rule/constraint:

(4) For the i-th register we want to describe how to evaluate the value $Value_i(q)$ (where $q$ is a limit). We divide into two cases:

(a) There is no "last" value $r$ (where $r<q$) at which $Value_i(r)=0$. In other words, there always exists a fundamental sequence $r_0,r_1,r_2,r_3,..$ for $q$ such that $Value_i(r_j)=0$ for all $j \in \mathbb{N}$. In this case set $Value_i(q)=0$.

(b) There is some "last" value $r$ (where $r<q$) at which $Value_i(r)=0$. In this case we assume that the value of register increases smoothly. That is, we define: $$Value_i(q)=sup(A) $$ where the set $A$ is defined as: $$A=\{\, Value_i(\alpha)\, |\, r<\alpha<q \}$$

There is "only one" exception to rule in (b), which always has to be observed. If according to rule in (b) $Value_i(q)=q$, then we always set $Value_i(q)=0$.

And now we can ask the following two questions:
(A) Suppose the number of registers used for some specific ordinal was equal to $n$. Then what is the smallest ordinal (presumably recursive) for which there exists no computable well-ordering (and a possible assignment of register values) such that the representation functions corresponding to $Value_1, Value_2,...Value_n$ are all recursive.

As an example, it seems "apparently" that highest one can go with two registers is $\varepsilon_0$. But how to prove/disprove it and what about arbitrary (but finite) number of registers?

(B) Suppose we are given two different computable well-orderings $N_A$ and $N_B$ (for same ordinal $p$). For the first well-ordering we describe a system of register values (satisfying contraints/rules (1) to (4) described in question), such that the representation functions (in $N_A$) corresponding to register values are all recursive. For the second well-ordering once again we describe a system of register values (presumably entirely distinct from the previous one), such that the representation functions (in $N_B$) corresponding to register values are again all recursive. Can we describe a case where isomorphism between $N_A$ and $N_B$ is not recursive (or show otherwise).

EDIT:

I will add one example so that question is a little clearer(unfortunately I don't know how I can shorten the main question any further). Suppose the $address:\omega \rightarrow \Bbb{N}$ function is: $$address(x)=x+1 \qquad if \; x \; is \; even$$ $$address(x)=x-1 \qquad if \; x \; is \; odd$$ The well-order relation corresponding to this is trivially recursive/computable.

Now if we are assuming two registers we have full choice in choosing our functions $Value_1:\omega \rightarrow \omega$ and $Value_2:\omega \rightarrow \omega$. We may choose: $$Value_1(x)=floor(x/2)$$ and $$Value_2(0)=0$$ $$Value_2(1)=0$$ $$Value_2(x)=0 \qquad if \; x \; is \; even \; and \; x\ne 0$$ $$Value_2(x)=1 \qquad if \; x \; is \; odd \; and \; x\ne 1$$ Now we have a computable well-ordering where the representation of successor functions and the functions $value_1:\Bbb{N}\rightarrow\Bbb{N}$ and $value_2:\Bbb{N}\rightarrow\Bbb{N}$ (which are representation functions of $Value_1$ and $Value_2$ respectively in the given well-ordering) are recursive. Writing them in full detail would be a little cubersome.

But the question is that whether there exists ANY choice for these two functions $Value_1$ and $Value_2$ such that there exists a computable well-ordering for $\omega$ for which the representation of successor function is non-recursive and yet the functions $value_1:\Bbb{N}\rightarrow\Bbb{N}$ and $value_2:\Bbb{N}\rightarrow\Bbb{N}$ will still be recursive.

Now actually thinking a bit more about it, one might ask whether the "computable" part in "computable well-ordering" is absolutely necessary or not. At any rate, I hope this makes the question a little clearer.

EDIT2:

Explanation for function $address:\alpha\rightarrow \Bbb{N}$. If we have a well-ordering on $\Bbb{N}$ whose order-type is $\alpha$, then position of each element of $\Bbb{N}$ is given by some $\beta$ (where $\beta < \alpha$). Furthermore for any two distinct numbers $a_1,a_2 \in \Bbb{N}$ ($a_1 \ne a_2$), if we denote the positions corresponding to $a_1$ and $a_2$ as $\alpha_1$ and $\alpha_2$ respectively then we have $\alpha_1 \ne \alpha_2$.

So essentially we have a function (say $position:\Bbb{N} \rightarrow \alpha$) which arises due to the well-ordering. The function $address:\alpha\rightarrow \Bbb{N}$ is just the inverse of the function $position$.

Answer 1

Unfortunately, I don't fully understand your question, concerning the registers.

But it seems that part of what is at stake is to find a computable relation on the natural numbers having order-type $\omega$, but where one cannot compute the isomorphism to $\langle\mathbb{N},<\rangle$. And this is something that I do understand, so let me tell you how it can be done.

Theorem. There is a computable relation $\newcommand\lt{\preccurlyeq}\lt$ on the natural numbers of order type $\omega$ such that the canonical isomorphism $\langle\newcommand\N{\mathbb{N}}\N,\lt\rangle\cong\langle\N,\leq\rangle$ is not computable. Consequently, the $\lt$-successor function on $\N$ also is not computable, and neither is the predecessor function.

Proof. The relation $\lt$ will be gradually revealed by the following process. First of all, all the even numbers will be ordered by $\lt$ the same as usual. Next, we start simulating all programs on empty input, giving each program additional time as the simulation proceeds. Whenever we find that program $e$ has halted, then we insert the next available odd number between $2e$ and $2(e+1)$ in the $\lt$-order. Note that since there are infinitely many halting programs, we will eventually use up all the odd numbers. Also, the relation $\lt$ is computable, since if we are given two numbers, we just run the process until those two numbers are placed into the order, at which time we know how they are ordered. The relation $\lt$ has order type $\omega$, since the order will be like the even numbers, but with sometimes an extra point being inserted between them, but only one new point for each successive even numbers.

Finally, the canonical isomorphism of $\langle\N,\lt\rangle$ with $\langle\N,\leq\rangle$ is not computable, since if we could tell whether $2e$ and $2(e+1)$ were adjacent, we could solve the halting problem. Similarly, we cannot compute the $\lt$ successor of $2e$, since if we could, then we could solve the halting problem by looking to see if it was even or odd. And similarly for the predecessor of $2(e+1)$. $\Box$

Answer 2

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$, the ordinal $\varphi(n-1,0)$ is the highest ordinal we can reach. We can prove the lower 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:

For each successor ordinal beyond $1$, we increment $Value_1$. This will result in $Value_1$ being reset to $0$ at every ordinal of the form $\omega^\alpha$, so if $\alpha$ has a Cantor Normal Form of $\omega^{\alpha_1} + \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$, we will have $Value_1(1+\alpha) = \omega^{\alpha_2} + \cdots + \omega^{\alpha_n}$.

For $Value_2$, we will increment it at every ordinal of the form $\omega^\alpha + 1$. Since $Value_1$ only resets at ordinals of the form $\omega^\alpha$, the values of $(Value_1,Value_2)$ will start from $(1,\alpha)$ and then $Value_1$ will be incremented until it resets to $(0,\alpha)$, and then $Value_2$ will be incremented. So there will be no repeats until $Value_2$ resets.

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.