1
$\begingroup$

Let's first define a function $H:\mathrm{Ord} \rightarrow \mathrm{Ord}$. Suppose we are given some ordinal $\alpha$ and we want to find $H(\alpha)$. We define $H(\alpha)$ as the supremum of halting times of all programs (such as OTMs for example) given only the parameter $\alpha$ (and nothing else).

Let's assume constructibility. Then I think it is not difficult to show that the function $H$ is non-decreasing over the countable ordinals. In other words for all countable ordinals $\alpha,\beta < \omega_1$ such that $\alpha<\beta$, we must have $H(\alpha) \leq H(\beta)$. However, as I understand, this is not necessarily the case as the input to $H$ starts to get $\geq \omega_1$. In other words there could exist some specific ordinals $\alpha,\beta \geq \omega_1$ such that $\alpha<\beta$ and $H(\alpha)>H(\beta)$. As a specific example, we could have $\beta=\omega_1 \cdot 2$ and $\alpha=\omega_1+k$ where $k$ is some suitably large countable ordinal. And if $k$ is large enough then we could have $H(\alpha)>H(\beta)$. Now if we think about it the reasoning behind it is fairly simple. Consider the example of $\alpha=\omega_1+k$ and $\beta=\omega_1 \cdot 2$. Let's denote the "count" of halting positions for programs with parameter $\omega_1 \cdot 2$ as $N(\omega_1 \cdot 2)$. The point here is that as soon as the countable ordinal $k$ becomes $\geq N(\omega_1 \cdot 2)$ we have $H(\alpha)>H(\beta)$. So basically, for sufficiently large $k$, we have $\alpha<\beta$, $N(\alpha)>N(\beta)$ and we get $H(\alpha)>H(\beta)$.

Now here is the question. What can be said (comprehensively) about various possibilities here? Is it possible that $\alpha<\beta$, $N(\alpha)<N(\beta)$ and we get $H(\alpha)>H(\beta)$. Similarly, suppose that we have $\alpha<\beta$, $N(\alpha)>N(\beta)$, $H(\alpha)>\beta$. Can we get $H(\alpha)<H(\beta)$? These are couple of possibilities while writing about this question (I haven't thought about the possibilities more systematically).

$\endgroup$
0

0

You must log in to answer this question.

Browse other questions tagged .