The surreal numbers are built up in a natural iterative process, by which at any ordinal stage, if one has two sets of surreal numbers $L$ and $R$, with every number $x_L$ in $L$ strictly below every number $x_R$ in $R$, then one creates if necessary a new surreal number situated between them, filling this gap. $$x=\{L\mid R\}$$ This also defines the order recursively. In general, we define a notion of equivalence, with the effect that all numbers created at a given stage filling the same gap in the earlier numbers are equal and $\{L\mid R\}$ denotes the first-born such number filling that gap. But there is also a canonical representation of every number, which avoids the need for the equivalence relation, where the $L$ and $R$ sets form a partition of the previously-created numbers. This canonical representation can be seen as essentially identical to the representation of surreals by binary $\{-1,1\}$ transfinite sequences, where a $1$ means move up from the preceding number and $-1$ means move down from it.

My question is about the restriction of the construction to what I shall call the *computable surreal numbers*.

Namely, let's simply define by recursion that a Turing machine program $e$ is a *computable surreal number* with value $\alpha_e$ if running program $e$ produces two enumerations—for simplicity let's use a multitape model with two output tapes—such that all the numbers appearing in the enumeration are programs that are themselves computable surreal numbers, and furthermore the values obey $\alpha_x<\alpha_y$ whenever $x$ appears on the first output tape and $y$ appears on the second output tape. In this case, the value of $e$ is
$$\alpha_e = \{\ \alpha_x\mid\alpha_y\ \},$$
where $x$ and $y$ range respectively over the numbers appearing in the first and second enumerations produced by $e$.

For example, the program that produces the empty sequence on each side will be a computable representation of the surreal number $0=\{\ \mid\ \}$. And then one can produce programs to produce $1=\{0\mid\ \}$ and $-1=\{\ \mid 0\}$, and so forth, in the usual process of building up the surreal numbers.

So ultimately this is a recursive definition of what it means to be a computable surreal number, and one can imagine the definition proceeding in a sequence of transfinite stages. One reaches in effect the smallest fixed-point, the smallest set of programs that fulfills the recursive definition.

One might prefer a representation closer to Kleene's $\cal O$, which would be fine with me, although I also find the recursive definition I gave above to have a clean simplicity.

It is not difficult to see that every computable ordinal, viewed as a surreal number in the obvious manner, will be a computable surreal number. Also, the computable surreal numbers will form an ordered field. It will be countable, of course, and hence not the same as $\text{No}(\omega_1^{CK})$, which is uncountable of size continuum.

- Are the computable surreal numbers a real-closed field?

It seems initially clear that they form a field, since we have the formulas for how to define addition, subtraction, multiplication, and division, and if we give these formulas programs that actually are surreal numbers, then (by transfinite induction) they will output programs that give computable surreal numbers. (See also my comment below.) I believe that one can similarly compute square roots of positive elements. I am less sure about every odd-degree polynomial having a root, although I fully expect this to be true.

The answer to the next question might seem obvious:

- Which real numbers are computable surreal numbers?

One might initially expect that these should be exactly the computable real numbers. But in light of the computable ordinal nature of the construction, it seems to me that perhaps one gets instead much more: the hyperarithmetic reals. For example, can we design a program that enumerates slightly better bounds on a surreal number according to the halting problem, so that the real number value that it exhibits will encode the halting problem? If so, I expect this to go all the way to the hyperarithmetic reals.

- Is the computable surreal field computably saturated?

I am not clear on how to prove that consistent computable types are realized.

Next, it seems to me that the set of computable surreal numbers (considered as a set of programs) will be $\Pi^1_1$-complete, as well as the equality relation $e=f$, and the order relation $e<f$. [**Update:** the relation $e<f$ is actually c.e. as a I prove in my answer below, and so $e=f$ is co-c.e.**Revised update.** The proposed proof that $e<f$ is c.e. was incorrect, and it now appears that the relation is complicated, as originally expected.]

For the upper bound, if we have an oracle for $\Pi^1_1$, then given any computable surreal number $e$, we can computably unwrap the underlying hereditary structure of the left and right sets and ask whether this is well-founded. Furthermore, we can ask about the hereditary order and equality on those numbers, which is uniquely determined by the recursion and so this will be $\Delta^1_1$.

For the lower bound, we can canonically interpret any purported computable well order into the surreal number formalism, and thereby reduce the well-foundedness of a linear order to the question whether a given program is a computable surreal number.

What remains are several further questions:

What is the complexity of the same-birthday relation, relating computable surreal numbers with the same birthday?

What is the complexity of the function that maps every computable surreal number $x$ to its canonical representation $\{L\mid R\}$, where $L$ consists of the earlier-born numbers below $x$ and $R$ consists of the earlier-born numbers above $x$?

What is the complexity of the function that maps every computable surreal number $x$ to the transfinite binary representation of $x$?

It seems likely that all these complexities are all $\Pi^1_1$-complete. Is that right? Perhaps same-birthday involves $\Sigma^1_1$, since one needs to match up the earlier birthdays, so this might push the complexity up.

Lastly, I might ask whether there are other accounts of the computable surreal numbers and whether they are different/equivalent to the account I described above.

28more comments