Koepke's paper Turing Computations on Ordinals defines a notion of "ordinal computability" using Turing machines with a tape the length of Ord and that can run for Ord-many steps, and shows that a set of ordinals is ordinal computable from a finite set of ordinal parameters if and only if it is an element of Gödel's constructible universe $L$.

Usually, whenever we have a notion of "computation", we can assemble the computations into a partial combinatory algebra (PCA), which can then be used to define a realizability topos. For example, the infinite time Turing machines of Hamkins and Lewis (which apparently predated and inspired Koepke's ordinal computations, having only a countably infinite tape but being allowed to run transfinitely long) were used by Bauer to construct a topos in which Baire space injects into the natural numbers.

I assume that Koepke's notion of ordinal computation gives rise to some kind of proper-class-sized PCA. (If it doesn't, please correct me!) If so, then it should also give rise to some kind of realizability category, although size issues might prevent this category from being a topos. My question is:

What is the relationship between this "ordinal realizability category" and Gödel's constructible universe $L$?

The ordinal realizability category is almost certainly not equivalent to the category $\mathrm{Set}_L$ of sets and functions in $L$. Among other reasons, realizability categories are usually non-Boolean and contain $\mathrm{Set} = \mathrm{Set}_V$ as the reflective subcategory of double-negation sheaves, but $L$ is already Boolean and not provably equivalent to the entire cumulative hierarchy $V$. However, it seems possible to me that $\mathrm{Set}_L$ might be some category of "discrete objects" in the ordinal realizability category.

In an ordinary realizability topos, the discrete objects are the subquotients of the natural numbers object, where the latter is the usual set of natural numbers embedded "discretely" with each natural number realized by a different computation (in contrast to the natural numbers sitting inside $\mathrm{Set}_V \subsetneq \mathcal{E}$ which are "indiscrete" with every number realized by the same computations). I would expect that for ordinal realizability there is a similar "discrete embedding" of all the ordinals into the realizability category, and a natural generalization of "discrete object" would be the subquotients of these ordinals, or maybe of finite products of them. Since these are in a different sense the objects "obtained by ordinal computation from a finite number of ordinals", it doesn't seem impossible that they might coincide with $\mathrm{Set}_L$, given Koepke's result about $L$.

However, even if this optimistic guess is wrong, it seems likely to me that there is *some* relationship between $L$ and the ordinal realizability category.

*(Thanks to James E Hanson, who made me aware of Koepke's result and helped me refine this question on the category theory Zulip.)*

9more comments