What do we know about the computable surreal numbers?

Question

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.

1. 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:

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

3. 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:

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

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

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

Answer 1

The reals which are computable surreals are precisely the hyperarithmetical reals, as you conjectured. I'll be making use of your argument that the field operations are effective (really just addition and subtraction, and the fact that we know how to create notations for $2^{-n}$).

In the one direction, every computable surreal notation has a rank $\alpha$, which is a computable ordinal. By induction (actually effective transfinite recursion), the corresponding real is computable from something like $0^{(2\alpha+1)}$.

---

In the other direction, I first claim that for any computable ordinal $\alpha$, from a $\Sigma^c_\alpha$ sentence we can uniformly obtain a notation which corresponds to $0$ if the sentence is false and $1$ if the sentence is true. Again this is effective transfinite recursion masquerading as induction. You already did the base case in your example of $\alpha_h$.

For the inductive step, if $\phi$ is $\Sigma^c_\alpha$, then $\phi = \bigvee_n \theta_n$, where the $\theta_n$ are all $\Pi^c_{<\alpha}$. Let $b_n$ be from the inductive hypothesis applied to $\neg \theta_n$. Then $\{ 0-b_n : n \in \omega \ | \ 2 \}$ is as desired for $\phi$.

Now let $x$ be some hyperarithmetical real. WLOG, $0 < x < 1$. We wish to give a notation. If $x$ is a dyadic rational, the result is immediate. Otherwise, there is some computable $\alpha$ such that for $q$ a dyadic rational and $n \in \omega$, "$x \in (q, q+2^{-n})$" is $\Sigma^c_\alpha$. For each dyadic rational $q \in (0, 1)$ and $n \in \omega$, let $b_{q, n}$ be as from the previous claim for this sentence. Then $x = \{ q +b_{q,n} - 1 : q, n \ | \ q + 2^{-n} + 1 - b_{q,n} : q, n\}$.

Edit: Thinking further, I don't need to handle the case that $x$ is dyadic separately. Everything I wrote after that is still true in that case.

---

Reciprocals. Note that if $y \neq 0$ is hyperarithmetic, then so is $1/y$. From this, it follows that if $y \neq 0$ is real and a computable surreal, then $1/y$ is also a computable surreal.

The process is mostly uniform: going from a hyperarithmetic real to a computable surreal real required a prior bounds (0 and 1 in my above writeup, but any computable bounds would have sufficed). So it will be uniformly computable if also given a rational bound away from 0: a rational $q$ with $|y| > q > 0$. Then we can use $-1/q < 1/y < 1/q$ as our bounds.

This is an example of a phenomenon known as level computability. The domain is an increasing union of sets, $\bigcup_n U_n$, where $U_n = (-\infty, -2^{-n}) \cup (2^{-n}, \infty)$. The function (reciprocal) is uniformly computable if in addition to being given a $y$ from the domain, it is also given an $n$ with $y \in U_n$.

---

Sign sequences. I'll show that the computable surreal numbers are precisely the ones with hyperarithmetic sign sequences. Going from computable surreal notation to hyperarithmetic sign sequence is again an effective transfinite recursion on the rank of the notation.

For the other direction, fix a computable ordinal $\delta$ and some $\emptyset^{(\alpha)}$. I claim that there is a uniform process that takes a $\beta < \delta$ and a partial $\emptyset^{(\alpha)}$-computable function $f: \beta \to \{+, -\}$ and produces a computable surreal notation $s_f$, such that if $f$ is total then $s_f$ corresponds to the surreal number represented by $f$. Again this is effective transfinite recursion on $\beta$, but I'll present it as induction.

First, consider the constant $+$ sequence of length $\delta$, and the constant $-$ sequence of length $\delta$. These serve as bounds for all the sequences we will be considering. It is straightforward to create computable surreal notations for them, so we can obtain a notation for their difference. Call it $d$. Now to the induction.

For $\beta = 0$, this is immediate.

For $\beta > 0$, fix some partial $\emptyset^{(\alpha)}$-computable function $f: \beta \to \{+,-\}$. We can list all pairs $(\gamma, g)$, where $\gamma < \beta$ and $g$ is a partial $\emptyset^{(\alpha)}$-computable function from $\gamma$ to $\{+,-\}$. The statement that $f$ and $g$ are both total, that $g$ is an initial segment of $f$, and that $f(\gamma) = +$ is $\Pi^0_2(\emptyset^{(\alpha)})$, so it is $\Sigma^c_{\alpha+3}$. So using the method described previously, we can make a $b_g$ which is 1 if this is true and 0 if it's false. Similarly, we make $c_g$ which is for the same statement, except $f(\gamma) = -$.

Now $s_f = \{ s_g - d + b_g\cdot d : (\gamma, g) \ | \ s_g + d - c_g\cdot d : (\gamma, g)\}$.

Note that if $f$ is partial, the left set of $s_f$ consists entirely of negative numbers and its right set entirely of positive numbers, so $s_f$ is a notation for 0.

Answer 2

Here is some partial progress. I claim that the computable surreal numbers include some noncomputable real numbers, confirming my guess in connection with question 2.

For each TM program $e$ we can write a program $h_e$ for a computable surreal number, which will have value $0$ if $\varphi_e(e)$ never halts and value $1$ otherwise. Namely, the program $h_e$ simply starts with a default of empty output streams, until such time as it observes $\varphi_e(e)$ to halt, when it places $0$ in the lower set. We can uniformly pass computably from $e$ to the program $h_e$, without knowing the answer to this question.

Let $h$ be the program that places the finite sum $\sum_{e\leq n}h_e2^{-e}$ into the lower set for each $n$ and similarly $(\sum_{e\leq n}h_e2^{-e})+2^{-n}$ into the upper set. That is, for each $e$ we are making the $e$th binary digit $1$ if $e$ halts. The lower set therefore has the supremum (in the reals) of the infinite binary sequence coding the halting problem. $$\alpha_h = \sum_e h_e2^{-e}$$ The upper set numbers, in contrast, are descending to this real from above, because of the extra $2^{-n}$ term, which exceeds all the rest of the corresponding infinite series.

Note that there is indeed a program $h$ that behaves this way, using the fact that addition is uniformly computable for the computable surreal numbers, and so we can uniformly produce the programs that produce these finite sums, even though we cannot compute the surreal values of the $h_e$ that are involved. Those finite sums are all dyadic rationals, but we don't really know exactly which ones.

The surreal number $\alpha_h$ that $h$ computes is the real number whose binary digits encode the halting problem, which is not a computable real number. And so there are noncomputable real numbers that arise as computable surreal numbers, as desired.

I believe similar methods will ultimately enable us to show that every hyperarithmetic real is a computable surreal number, but I don't quite see my way through the details.

If someone has a nice approach or even just some small further progress, please post an answer.

Update for c.e. reals. Let me explain how the idea adapts to show that every c.e. real arises as a computable surreal number. Suppose that $x$ is a left-c.e. real, which means that there is a computable procedure to enumerate a sequence of rational numbers of which $x$ is the supremum. We may assume that $x$ is irrational. It is not difficult to see that $x=N+\sum_{k\in X}2^{-k}$ for some integer $N$ and c.e. set $X\subseteq\mathbb{N}$.

For each natural number $k$, let $r_k$ be the program whose surreal value is $0$ or $1$, respectively, depending on whether $k\in X$. This program starts with default empty output streams, until it sees $k$ enumerated into $X$, at which time it places $0$ in the lower set, making the resulting surreal value $1$. Now, let $r$ be the program that for each $n$ places $N+\sum_{k\leq n}r_k2^{-k}$ into the lower sets and $(N+\sum_{k\leq n}r_k2^{-k})+2^{-n}$ into the upper sets. So these numbers converge to the value $$\alpha_r = N+\sum_k r_k2^{-k},$$ which in light of the definition of $r_k$ is the same as the target value $x$. So $x$ is a computable surreal number, as desired.

A similar idea works with right c.e. reals, and so every c.e. real is a computable surreal number. So also are the d.c.e. reals, because we can computably substract.

Answer 3

Let me explicate fuller details about the computable surreal number operations. Let's start by showing that they form a ring.

Theorem. The computable surreal numbers form a ring.

Proof. We have to show that the computable surreal numbers are closed under addition, subtraction, and multiplication.

Surreal addition $x+y$ is defined recursively as follows: $$x+y=\left\{\ x+y_L\quad x_L+y\bigm\vert x+y_R\quad x_R+y\ \right\}.$$ We are using here the usual convention that $x_L$ and $x_R$ range over the left and right sets of $x$, respectively, and similarly for $y$.

It might seem initially unsurmountable to make this computable, since in order to produce the program for $x+y$, we might think that we have to undertake a transfinite recursion in order first to compute $x+y_L$ and so forth.

Nevertheless, I claim that we don't need to mount that recursion. In fact, there is a computable procedure to produce a program realizing $x+y$ as a computable surreal number, given programs for $x$ and $y$. The reason is that by the Kleene recursion theorem, there is a program solving the recursion expressed by the definition of $x+y$. That is, there is a program that takes programs for $x$ and $y$, starts enumerating the left and right sets, and then applies that same addition program to compute the values $x+y_L$, $x_L+y$ and so forth, as the values of $x_L$, $y_L$, $x_R$, $y_R$ are enumerated by $x$ and $y$. So we can computably produce the programs that will exhibit $x+y$ as a computable surreal number.

The same idea works with negation and subtraction $$\newcommand\unaryminus{-}\unaryminus x=\{\ \unaryminus X_R\mid\unaryminus X_L\ \}.$$ By the notation $\unaryminus X_R$ here we mean the set of all $\unaryminus x_R$ for $x_R\in X_R$, and similarly with $\unaryminus X_L$. Using this, we define subtraction simply as adding the negation: $$y-x=y+(\unaryminus x).$$ By applying the Kleene recursion theorem, there is a uniform computable procedure to produce $-x$ and $x-y$ from programs for $x$ and $y$.

Similarly with multiplication, which is defined by $$x\cdot y =\{\ X_{L}\mid X_{R}\ \}\cdot \{\ Y_{L}\mid Y_{R}\ \}=$$ $$=\{\ x_Ly+xy_{L}-x_{L}y_{L}\quad x_{R}y+xy_{R}-x_{R}y_{R}\ \mid\ x_{L}y+xy_{R}-x_{L} y_{R}\quad xy_{L}+x_{R}y-x_{R}y_{L}\ \}$$ By the Kleene recursion theorem, there is a multiplication program that obeys this recursive definition. As numbers get enumerated into the left and right side of $x$ and $y$, we apply that program suitably so as to carry out this definition of $xy$. $\Box$

To get that the computable surreals are a field, we would need division. For reciprocal and division, see the formula on the Wikipedia entry. Notice that for positive $y$ the formula is applied only with positive values of $y_L$, and so we would seem to need to be able to compute the order.

I had posted initially that the order $x<y$ was a c.e. relation, and then argued as a consequence that this was enough to apply the Kleene recursion theorem method to show that division $x/y$ (by nonzero) was computable.

But the c.e. argument was not correct (pointed out by Dan Turetsky in the comments). And so we don't currently know that the computable surreals form a field, and perhaps the evidence is now against this. See also this related unanswered question of Mike Shulman.

Lastly, regarding saturation, let me prove the following:

Theorem. The order on the computable surreal numbers is computably saturated, in the sense that every c.e. cut is filled. That is,if $X$ and $Y$ are c.e. sets of computable surreal numbers, with every element of $X$ below every element of $Y$, then there is a computable surreal number strictly between.

Proof. This is obvious, since $x=\{\ X\mid Y\ \}$ will be a computable surreal number strictly between, if we have computable enumerations of $X$ and $Y$. $\Box$

Answer 4

I did indeed find the (or at least a) definition of $\sqrt{x}$ for surreal $x$ in On Numbers And Games (page 22 of the second edition). It looks like this:

$$\sqrt{x}=y=\left\{\sqrt{x^L}, \dfrac{x+y^Ly^R}{y^L+y^R}\right|\left.\sqrt{x^R},\dfrac{x+y^Ly^{L*}}{y^L+y^{L*}}, \dfrac{x+y^Ry^{R*}}{y^R+y^{R*}}\right\}$$

with $x^L$ and $x^R$ the options of $x$ and $y^L$, $y^{L*}$, $y^R$, $y^{R*}$ options of $y$, chosen so that none of the denominators is zero. Note that this builds $y$ in an iterative fashion, using previous options to find new ones. The definition of $\dfrac1x$ does much the same (note that this definition assumes WLOG that $x\gt 0$) : $$\dfrac1x=y=\left\{0, \dfrac{1+(x^R-x)y^L}{x^R}, \dfrac{1+(x^L-x)y^R}{x^L} \right|\left. \dfrac{1+(x^L-x)y^L}{x^L}, \dfrac{1+(x^R-x)y^R}{x^R}\right\}$$ ONAG's example/explanation for this definition goes something like this: take $x=\{2|\}=3$. Then there is no $x^R$ and the only $x^L$ is 2, so the formula for y becomes $y=\{0, \frac12(1-y^R)|\frac12(1-y^L)\}$. Now, initially we have only $0$ for $y^L$ so the first $y^R$ is $\frac12$; the next $y^L$ is then $\frac12(1-\frac12)=\frac14$, the next $y^R$ is $\frac12(1-\frac14)=\frac38$, etc. It's certainly plausible that the Recursion Theorem still works here to ensure computability, but I'm substantially less sure.