7
$\begingroup$

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

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.