2
$\begingroup$

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$.

$\endgroup$
8
  • 2
    $\begingroup$ Your question is not asked in a clear manner, and this is likely why it is not getting attention. I would encourage you to find a more direct clearer way to express your question. For example, you seem to be asking for an example of a computable relation with order type $\omega$, whose successor function is not computable (and this much is easy to do), plus something else complicated about "registers." Can you describe what you are trying to do more clearly? $\endgroup$ Aug 21, 2017 at 15:24
  • $\begingroup$ Can you say in a sentence or two what the registers are for? $\endgroup$ Aug 21, 2017 at 15:38
  • $\begingroup$ Just in a sentence, the registers/variables just mean that a certain sub-set of computable well-orderings (for a given ordinal) will be admitted. Also, the first part is actually just about finding a computable relation for $\omega$ for which successor isn't computable. However, note that this is the second condition in the question (towards the end). The first condition before that must also be satisfied. $\endgroup$
    – SSequence
    Aug 21, 2017 at 16:24
  • $\begingroup$ @JoelDavidHamkins Also the three conditions for register values (in first part of question) are just constraints. The register values can change in any conceivable way as long as the required constraints are satisfied. With one register for example, for $\omega$, there is no choice for register value except to make it equal to predecessor function (due to set-up of constraints). In the case of two registers this is no longer the case (the three constraints described in first part can be satisfied in a myriad of different ways). $\endgroup$
    – SSequence
    Aug 21, 2017 at 16:31
  • $\begingroup$ "However, note that this is the second condition in the question (towards the end). The first condition before that must also be satisfied." What I meant with this (more clearly) is that both of the conditions must be satisfied simultaneously by a given well-ordering. $\endgroup$
    – SSequence
    Aug 21, 2017 at 16:37

2 Answers 2

3
$\begingroup$

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$

$\endgroup$
16
  • $\begingroup$ It seems I gave a similar construction already on your previous question: mathoverflow.net/a/278049/1946. Perhaps the current way of doing it is a bit simpler. $\endgroup$ Aug 21, 2017 at 17:14
  • $\begingroup$ I will try to give a very specific example. Considering the case of $\omega$, if we had one register the way constraints are described for register in first part we will have a function $Value_1:\omega \rightarrow \omega$ such that:$Value_1(x)=x-1$ (truncated subtraction by 1). However, for example, that forces the "representation function" corresponding to $Value_1$ such that we can always compute the successor function (or in terminology I described in question the "representation function" corresponding to successor function) in $\omega$ for the given well-ordering. $\endgroup$
    – SSequence
    Aug 21, 2017 at 17:16
  • 1
    $\begingroup$ Sorry, I still have no idea what you want. $\endgroup$ Aug 21, 2017 at 17:21
  • 2
    $\begingroup$ In particular, what is needed is not "examples," but rather: further clarity in what the question is actually asking. $\endgroup$ Aug 21, 2017 at 17:36
  • 3
    $\begingroup$ Sorry, I still don't really understand your question exactly, and so I'll be moving on. In your last comment, for example, you don't seem to insist on any connection between the order and the value functions, which I don't think is what you instend. Basically, this question is a mess, and if I were you, I would edit by rewriting the question from scratch. In the future, I'd recommend aiming for far greater clarity in your mathematical writiing. Write grammatically correct sentences. Use standard terminology. Define your terms clearly. Make a clear question statement. $\endgroup$ Aug 22, 2017 at 11:44
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I am not certain about the reasoning related to first part of question. For the second, I think one would expect lower bounds similar to what you have described (so I suppose it is most likely correct). Though just pointing one particular point in question2(A): One also has to make sure the representation functions (corresponding to register values) will be recursive in some recursive well-ordering (for the ordinals of form $\varphi(n-1,0)$ that you are describing). Though certainly that would be the case for system of register values you described. $\endgroup$
    – SSequence
    Aug 24, 2017 at 14:10
  • $\begingroup$ I think if one can prove that the lower bounds you provided for question2(A) are also upper bounds, then that would resolve that particular part of question. $\endgroup$
    – SSequence
    Aug 24, 2017 at 14:14
  • $\begingroup$ The first part of question remains unresolved (in terms of reasoning of why it should be true, if it is). That's because if a given register value (say the function is $Value_1$) is allowed to repeat (which does happen in case of two registers), then it isn't possible (even for $\omega$) in general to extract the representation of successor function from the representation of function $Value_1$ alone. $\endgroup$
    – SSequence
    Aug 25, 2017 at 6:56
  • $\begingroup$ Small note: I used the phrases "representation of $Value_1$" and "representation of successor function" interchangeably "representation function of $Value_1$" and "representation function of successor function" respectively to make it a little easier to read. It is already clear that we have only one well-ordering relation that is under consideration (so there is no ambiguity in that regard). $\endgroup$
    – SSequence
    Aug 25, 2017 at 7:18
  • $\begingroup$ Good work with the edit. So, assuming this to be correct (which I assume it quite likely is), this would settle the question2(A). I will be perusing it slowly. So this leaves question1(question in first part) and question2(B), both of which relate to isomorphism. $\endgroup$
    – SSequence
    Aug 26, 2017 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.