Let $A$ and $B$ denote two *countably infinite* sets of ordinals.


Let $W\_A$ denote the supremum of ordinals *writable* by Ordinal Turing Machines with the set $A$ given as the source of parameters. That is, for any element $\tau$ of $A$, a $\tau$-th cell of the input tape is marked with $1$ before the start of a computation.


Similarly, let $W\_B$ denote the supremum of ordinals *writable* by Ordinal Turing Machines with the set $B$ given as the source of parameters. That is, for any element $\tau$ of $B$, a $\tau$-th cell of the input tape is marked with $1$ before the start of a computation.


Here “an ordinal writable by Ordinal Turing Machines” implies a countable ordinal $\alpha$ such that an Ordinal Turing Machine halts with an infinite binary sequence (written in the initial segment of length $\omega$ on the output tape) which encodes a well-ordering of natural numbers of order-type $\alpha$.


Question: do there exist a pair of $A$ and $B$ such that the supremum of all elements of $A$ is greater than the supremum of all elements of $B$, yet $W\_A < W\_B$? If no, why? The question separates into two possible situations: (i) an element in $A$ or $B$ may be uncountable; (ii) all elements in $A$ and $B$ are countable.



Countably infinite sets of ordinals as parameters for Ordinal Turing Machines
The answer is yes. In fact, you can make the difference enormous.


First, let me construct a certain set of ordinals.


**Lemma.** There is a countable set $X$ of ordinals such that:


1. Every OTM program that halts with $X$ as input, halts strictly before $\sup X$.
2. If a program does not halt with $X$ as input, then there is no countable end-extension $Y\supset X$ for which the program would halt on input $Y$.


**Proof.** We can construct $X$ in stages. Enumerate the programs $p\_0$, $p\_1$, and so on. To begin, start with any countable set $X\_0$. If $X\_n$ is defined, ask whether there is some countable end-extension of it to $X\_{n+1}$, extending only above the space used by the earlier programs, in such a way that $p\_n$ halts with this new input oracle. Let $X=\bigcup\_n X\_n$ be the limit oracle. This set is countable, and it has the two properties by construction. The computation of any program that halts was preserved, since the new ordinals were added only beyond the use of that program. And if a program does not halt with $X$, then no end-extension would make it halt, since otherwise we would have done so at the stage that that program was considered. $\quad\Box$


To form the desired sets $A$ and $B$, let $\alpha$ be any ordinal larger than $\sup X$. Let $A=X\cup\{\alpha+n\mid n\in\omega\}$. And let $B=\omega\cup\{\alpha\}$.


Notice that $\sup B<\sup A$. But by the lemma, the possible outputs of computations with $A$ are the same as the possible outputs from $X$, since $A$ end-extends $X$. Basically, the extra stuff we added on top of $A$ was no help in any computation, since all the computations used only the $X$ part and never got out to $\alpha$. But with $B$ as an oracle, we can search for the input $\alpha$ and thereby use $\alpha$ in effect as an input. So anything that $\alpha$ can write is also $B$-writable. In particular, with $B$ we can give $\alpha$ itself as output, but all ordinal outputs with $A$ are less than $\alpha$.


(If you want to consider reals coding ordinals, then we can find an $\alpha$ such that from $\alpha$ we can write a real coding an ordinal bigger than any ordinal coded by output from $X$. For this, we do the whole construction inside $L$, so $X$ is in $L$, and then pick $\alpha$ so that in $L\_\alpha$ we can define a real coding an ordinal larger than the countably many ordinals coded by reals output by $A$. Now, from $B$ we can compute $\alpha$ and therefore $L\_\alpha$ and therefore give this real as output.)


By choosing $\alpha$ suitably, therefore, we shall have $B<A$ but $W\_B>W\_A$, as desired.


**Moral.** The main idea is that we hid $\alpha$ from $A$, since it got lost in the complexities of $X$, and no program could find $\alpha$ at the top. But $\alpha$ is not hidden in $B$, because it is the only infinite ordinal in $B$, and so a program can easily find it.


