Gaps in the ordinals writable by Ordinal Turing Machines with a single countable parameter

Question

Let $W(\alpha)$ denote the set of all (countable) ordinals writable by Ordinal Turing Machines with a single (countable) parameter $\alpha$, i.e. each computation starts with a single ($\alpha$-th) cell on the input tape marked with a non-zero symbol (all other cells are marked with a zero symbol).

Question: does there exist an ordinal $\beta$ such that there exists at least one ordinal $\gamma < \beta$ such that $\gamma \notin W(\beta)?$ If no, why? If yes, how large is the smallest such $\beta$?

Answer 1

The answer is yes. For example, take $\beta=\omega_1$, the first uncountable ordinal. Since there are only countably many programs, there can be only countably many writable ordinals relative to $\beta$ as input. But there are uncountably many ordinals $\gamma$ below $\beta$, and so most of them are not writable from $\beta$.

The smallest such ordinal will be exactly $\omega_1^L$. To see this, consider any $\beta<\omega_1^L$. Thus, $\beta$ is countable in $L$, and this will be revealed in some countable stage of the constructibility hierarchy $L_\eta$. Consider the algorithm that on input $\beta$ begins to construct copies of the constructible hierarchy until it finds a stage $L_\eta$ that can see that $\beta$ is countable. Thus, this structure provides an $\omega$-enumeration of the ordinals $\gamma<\beta$. Therefore they will all be writable from $\beta$, since there will be a program that searches for this $L_\eta$ and then writes the $n$th such $\gamma$ in that enumeration.