The recursion this site cannot run

The construction that produces the numbers has no stopping rule in it.

A number is $\{L \mid R\}$ where $L$ and $R$ are sets of previously constructed numbers with every member of $L$ below every member of $R$. Nothing in that says the sets are finite, and nothing says the days stop.

That is not an oversight in the definition. The construction was read off games rather than designed, and a game’s option sets are whatever the position offers — so there was never a reason to bound them, and bounding them would have excluded objects the theory wants.

Run it past every finite day and the objects it produces are no longer things this site can hold.

What the finite days produce #

Day 0 is $\{\ \mid\ \} = 0$. Day 1 adds $1 = \{0 \mid\ \}$ and $-1 = \{\ \mid 0\}$. Every later day puts the simplest number into every gap the previous days left.

After five days there are 63 numbers, and every one of them is a dyadic rational — a fraction with a power of two underneath. That is checked by the figure rather than assumed, and it is not an accident: each day halves the smallest gap, so denominators double and nothing else can appear.

The important consequence is negative. One third is on no finite day. It is not that the construction has not reached it yet in the sense that a bigger number is not reached yet; it is that no finite day contains it, at all, ever.

Those same days can be read as a tree rather than as a stack of lines, and the second reading is the one that explains the counting. Reading down a branch is reading a sequence of moves in a game, and a number’s day is the length of that sequence — which is why a number born on day $n$ is a position whose play lasts $n$ moves, and why the days are the right unit for anything about depth.

The pattern of the finite days, stated exactly #

Before leaving the computable part it is worth stating what it contains, because the count is unusually clean.

Day $d$ produces $2^d$ new numbers, so after $d$ days there are $2^{d+1} - 1$ of them. Five days gives 63, which is what the figure draws. Each day puts exactly one number into every gap the previous days left, and the count doubles because the gaps do.

What the new numbers are is more interesting than the count, and it is not one denominator per day. Day 3 produces $\pm 3$, $\pm\tfrac32$, $\pm\tfrac14$ and $\pm\tfrac34$ — denominators $1$, $2$ and $4$ all at once. Day 4 produces denominators $1$, $2$, $4$ and $8$.

The pattern is about where on the line each one sits. On day $d$, a number born strictly between the integers $k$ and $k+1$ has denominator $2^{\,d-1-k}$: eighths between $0$ and $1$ on day four, quarters between $1$ and $2$, halves between $2$ and $3$, and the integer $4$ itself at the end.

So the construction spends its resolution near zero, and every step outward costs a halving. That is the simplicity rule showing its shape: the simplest number in a gap is the one with the earliest birthday, and being far from the origin is itself a kind of lateness.

The rule producing every one of them is the simplicity rule: the earliest-born number strictly between the two options. Applied to a gap whose ends arrived on day $d-1$, the earliest-born number strictly inside is the halfway point, which is why denominators double once per day and never do anything else. The pattern above is that single fact, read off a line instead of out of a definition.

Three objects past the edge #

ω, the first infinite ordinal, is $\{0, 1, 2, 3, \ldots \mid\ \}$: Left may move to any integer, Right cannot move at all. It is greater than every integer, and it is a perfectly good number in the construction.

1/ω is $\{0 \mid 1, \tfrac12, \tfrac14, \tfrac18, \ldots\}$: positive, and below every positive dyadic. It is the reciprocal of ω in the field structure, and it is an infinitesimal — though not the same kind as up, which is a game rather than a number.

⅓ is $\{0, \tfrac14, \tfrac5{16}, \ldots \mid 1, \tfrac12, \tfrac38, \ldots\}$: the two sequences of binary approximations closing in from either side, and neither sequence terminates.

All three need an infinite option set, and that is exactly what this site’s game() cannot take: it interns a position from a finite list, keyed on the identities of the options. There is no representation of an infinite list to key on.

Why ω is a number and not a game #

There is a distinction here that has to be made carefully, because both objects are built by the same recursion out of the same brackets.

A game is $\{L \mid R\}$ with no condition on $L$ and $R$ at all. A number is a game in which every member of $L$ is strictly less than every member of $R$.

ω satisfies the condition vacuously: $R$ is empty, so there is nothing for the members of $L$ to be less than. It is a number.

$\{0 \mid 0\} = *$ does not: 0 is not less than 0. It is a game and not a number, and it is confused with zero — the position where whoever moves wins.

So the same construction produces both, and the inequality is the entire separator. Removing the stopping condition changes how far the construction goes; it does not change which of the two things any particular result is.

Read as outcomes the separator is just as sharp. A number is a position in which neither player is eager, so it never lands in the class where whoever moves first wins — and every position in that class is a game and not a number, however the construction happened to reach it. Removing the stopping rule adds objects to both sides of that line and moves nothing across it.

What “day ω” means, precisely #

The phrase is doing real work and deserves unpacking, because “past every finite day” sounds like hand-waving and is not.

The days are indexed by ordinals, and ω is the first ordinal after all the finite ones. Day ω’s numbers are built from option sets drawn from everything built on any finite day — which is a legitimate collection, so the construction is well defined.

What arrives on day ω is: every real number, ω itself, 1/ω, and a great deal else. What arrives on day ω + 1 is more, and the construction continues through the ordinals without ever stopping.

This is where the object stops being something a program can hold, and the reason is not subtle: day ω’s option sets are infinite, and a machine that interns positions from finite lists has no representation for one. There is no clever encoding that fixes this, because the difficulty is the cardinality rather than the format.

Which says why one third is unreachable and ω is not far away #

That reading of the finite days sharpens both of the essay’s boundary cases, and it separates two things the phrase “past every finite day” runs together.

One third is unreachable because it is never anybody’s gap. Every gap at every finite stage has dyadic ends, and the simplest number strictly inside a gap with dyadic ends is another dyadic. So the construction keeps producing better approximations to a third — $\tfrac14$, then $\tfrac5{16}$, then $\tfrac{11}{32}$ — and each of them fills a gap that a third was also inside. It is passed over an unbounded number of times and produced never, not because it is far away but because it is never the simplest thing in any gap.

ω is unreachable for the opposite reason. It is not squeezed between things; it is beyond all of them, and its option set is $\{0, 1, 2, \ldots\}$ — an infinite list with no last member. Nothing about denominators is involved.

So the two objects fail the finite construction in two different ways, and lumping them together as past every finite day hides the difference. One is a limit from inside a gap that never closes; the other is a limit from outside a set that never ends. Day ω supplies both, and it supplies them by allowing infinite option sets — which is the one change, and it answers both problems at once.

And why the machinery’s boundary sits exactly there #

That is also the cleanest statement of what this site’s evaluator can and cannot do, and it is narrower than “finite”.

game() takes a finite list. Every position on every finite day has one, because a canonical form’s options are drawn from the day below and there are finitely many of those. So the evaluator’s reach is not an arbitrary engineering limit that a larger machine would push back — it is exactly the finite days, and it is exactly where infinite option sets begin.

One more day and no amount of memory helps. The obstruction is not that ω’s option set is large; it is that there is no last element to key on, and interning is keyed on the identities of the options. A machine with unbounded memory and unbounded time would fail in the same place and for the same reason.

That is a boundary worth being precise about, because “the code cannot go further” usually means not yet and here it means not ever. Everything below day ω is a matter of patience; day ω is a matter of representation.

Why the boundary is worth drawing rather than hiding #

It would be easy to write about ω without noticing that nothing here computes it. The site’s seventh invariant forbids that: never claim to have solved what the code cannot evaluate.

The alternative — omit the infinite objects entirely — is worse, because it presents the construction as though the dyadics were the destination. They are not; they are what a machine with finite memory reaches.

So the figure does the third thing: computes the finite part, prints the option sets of the infinite part, and states the reason for the difference. The reason is not deep and that is why it is worth printing — it is an implementation limit, not a mathematical one, and saying which is which is most of the value.

There is a family of objects this site can compute that answers to almost the same description, and the fact that it is a different family is the sharpest thing on this page. Up, its multiples and their stars are positive and smaller than every positive number, which is word for word what was said of $1/\omega$ two paragraphs ago — and they are games rather than numbers, so they sit in a different part of the structure entirely.

The surprise: infinitesimal games and infinitesimal numbers are different things #

This trips almost everybody, and the construction above is what makes it precise.

1/ω is a number. It is positive, it is smaller than every positive real, and it is totally ordered with respect to everything else — for any $x$, one of $x < 1/\omega$, $x = 1/\omega$, $x > 1/\omega$ holds.

Up is not a number. It is positive and smaller than every positive number, so it sounds identical — and it is confused with star, meaning neither above, below, nor equal. A number cannot be confused with anything, by definition.

So the two objects satisfy the same informal description and sit in different parts of the theory, and the separator is an inequality test that this site’s compare performs directly.

What the finite part is good for anyway #

It would be a mistake to read the boundary as a shortfall, because the finite part is not a truncated version of the infinite object. It is the part that corresponds to games somebody plays.

Every position with a finite game tree has a finite birthday, so every position drawn anywhere on this site has a value that lives in the part the machinery reaches. The infinite objects are reached by the construction and are not reached by any position a reader could sit down at.

That is worth saying because it changes what the boundary means. It is not “this site computes a fragment of the theory”; it is “this site computes the whole of the theory of finite games, and the construction happens to continue past them”.

What a bigger budget buys is worth stating exactly, because the natural picture of it is wrong. Another day gives more dyadics in a denser arrangement and not one object of a different kind. Extending the computation does not approach the infinite part at all, because the infinite part is not at the end of the finite one — it is what arrives when infinite option sets are permitted, and no number of finite days permits one.

The reciprocal, and why it is worth a mention #

$1/\omega$ is the object that makes the surreals a field rather than merely an ordered group, and it is worth a paragraph because its existence is not obvious.

ω is bigger than every integer. Its reciprocal must be positive and smaller than every positive real, and there is no such real — so in the reals the equation has no solution and the construction has to supply one. It does: $\{0 \mid 1, \tfrac12, \tfrac14, \ldots\}$ is positive, is below every positive dyadic, and multiplies with ω to give 1.

None of that is computed here. Multiplication of surreals is defined by another recursion, this site does not implement it, and the claim above is stated on the theory’s authority rather than on any arithmetic performed on this page. That is exactly the situation the seventh invariant is about, and the correct response is to say so rather than to imply otherwise.

Where the model stops #

Everything drawn here is a finite day. The claim that all finite days give dyadics is checked over the days computed and proved in general by the halving argument; the claim about ω is not checked at all, and is presented as a definition rather than as a computation.

And the field structure is asserted. That the surreals form an ordered field, that ω has a reciprocal, that $\omega - 1$ and $\sqrt\omega$ exist — none of that is computed here and none of it could be. It is stated because it is the reason the construction is interesting and it is flagged as being outside what this site checks.

What the picture cannot show #

The finite days draw as points on a line and the line is the wrong shape.

The finished object is a proper class — too big to be a set — and contains elements no drawn interval accommodates: ω is not off to the right of the picture, because there is no rightward direction in which it lies at a distance. The picture’s implication that the construction is filling in a line is right about the dyadics and wrong about the destination.

A comparison worth making #

The boundary drawn here is an implementation limit. It is worth contrasting with the other two kinds of limit this site records, because the three get confused.

An implementation limit: the code cannot represent the object. Fixable in principle by better code, and the fix here would mean a different representation of games entirely.

A computational limit: the object is representable and the computation is too expensive. That is most of the complexity field — a Domineering board of 8 × 8 is perfectly representable and its value is out of reach.

And a mathematical limit: no computation of any size settles it. The octal periodicity conjecture is one; whether a given octal game is eventually periodic is not known to be decidable at all.

The three are often reported with the same phrase — this site cannot show that — and they mean quite different things about whether anybody could.

What a reader should take from a figure that refuses #

There is a design question underneath all of this, and it is worth answering out loud because the alternative is common.

A figure that cannot draw something has three options. It can draw an approximation and hope nobody reads the caption too closely. It can omit the object and let the reader assume the picture is complete. Or it can name what it cannot draw and say why.

The first two are how this material is usually presented, and both mislead in the same direction: they suggest that the finite dyadics are what the construction produces, full stop.

The third is what the hero figure does, and the cost is that a reader has to accept a paragraph of text where a picture would be. That seems a fair trade for the alternative being wrong.

Take the budget down as far as it will go and the point stops being suggestive. Two days is the least that draws anything with a gap in it, and the objects underneath are unchanged.

One consequence for everything else here #

The boundary has a practical effect on the rest of this site, and it is worth stating so that it does not look like an isolated curiosity.

Every value printed anywhere here is a finite object, because every position drawn is finite. So the notation, the canonical forms, the comparisons and the sums are all operations on finite trees, and the machinery that performs them is ordinary recursion with memoisation.

The moment an infinite option set enters, none of that applies: canonical form is not defined by the same reduction, comparison is not decided by playing a difference to the end, and the sum is not computed by the same recursion. The theory has answers for all of it and this site’s code has none, and the two facts are independent.

A note on what “cannot” means here #

The title says this site cannot run the recursion, and the honest version is narrower: this site’s representation of a game cannot hold a position with infinitely many options.

A different representation could. Symbolic systems that manipulate surreal numbers exist, and they work by treating the option sets as descriptions rather than as lists — which is a perfectly good approach and a completely different program from the one this site is.

The reason not to build it here is that the site’s whole claim rests on values being computed from positions by the recursion, and a symbolic system computes from descriptions instead. It would produce correct answers by a method the rest of the site does not use, which is a worse outcome than saying where the method stops.

Where the ladder goes next #

This anchor’s rungs build the numbers, explain the rule that picks them, and record that the order of discovery ran from games to numbers. This rung is the boundary of what the machinery reaches. Onward is the part of the structure that is games rather than numbers — the infinitesimals, the switches, and everything with an option set the two players disagree about.