2
$\begingroup$

This question is based on the assumption that all computations start with no ordinal parameters (i.e. the input is empty).

The term “stabilization time of a machine” for this question implies the successor of $\alpha$, where $\alpha$ is the least ordinal such that the values of all symbols written on all cells of the initial segment of length $\omega$ of the output tape never change at any time $\beta > \alpha$. If a machine diverges (i.e. the initial segment of length $\omega$ of the output tape does not stabilize), then the stabilization time of such machine is $0$.

Consider Ordinal Turing Machines with no oracle. Let us call such machines “$0$-th order machines”. There exists the supremum of stabilization times (let us denote it by $\sigma(0)$) of these machines.

Consider Ordinal Turing Machines with the oracle tape. This additional tape has a single cell (namely, the $\sigma(0)$-th one) marked by a non-zero symbol. Let us call such machines “$1$-st order machines”. There exists the supremum of stabilization times (let us denote it by $\sigma(1)$) of these machines.

Then consider Ordinal Turing Machines with the oracle tape where two cells (namely, the $\sigma(0)$-th and $\sigma(1)$-th ones) are marked by non-zero symbols. Let us call such machines “$2$-nd order machines”. There exists the supremum of stabilization times (let us denote it by $\sigma(2)$) of these machines.

Similarly, one can define the ordinals $\sigma(n)$ for any natural number $n$.

The oracle tape of the $\omega$-th order machines contains $\omega$ many cells marked by non-zero symbols: a particular cell corresponds to some $\sigma(n)$. There exists the supremum of stabilization times (let us denote it by $\sigma(\omega)$) of these machines.

We can continue: the oracle tape of the $(\omega+1)$-th order machines contains $\omega+1$ many cells marked by non-zero symbols: a particular cell corresponds to some $\sigma(\alpha)$, where $\alpha < \omega+1$. Note that the $\sigma(\omega)$-th cell is the last cell of the oracle tape marked by a non-zero symbol. There exists the supremum of stabilization times (let us denote it by $\sigma(\omega+1)$) of these machines.

Can we continue the similar logic unboundedly and define the class $\mathsf{S}$ of ordinals of the form $\sigma(\beta)$, where $\beta$ may be an arbitrarily large (possibly uncountable) ordinal?

If no, why?

If yes, consider Ordinal Turing Machines with the oracle tape where an $\alpha$-th cell is marked by a non-zero symbol if and only if $\alpha$ belongs to $\mathsf{S}$ (i.e. if and only if $\alpha = \sigma(\beta)$ for some ordinal $\beta$). Let us call such machines “$\mathsf{S}$-machines”.

Let $\tau(0)$ denote the supremum of countable ordinals eventually writable by $\mathsf{S}$-machines on the initial segment of length $\omega$ of the output tape.

Let $\mu(3)$ denote the least ordinal $\delta$ such that $L_{\delta} \prec_{\Sigma_3} L_{\omega_1}$. This ordinal is mentioned in this comment and this answer on Mathoverflow.

Question: which ordinal is larger, $\tau(0)$ or $\mu(3)$?

(I do not know whether the answers depend on the acceptance of the axiom of constructibility, but if they do, I am interested in both cases.)

$\endgroup$
2
  • 2
    $\begingroup$ "Can we continue the similar logic unboundedly and define the class $\mathsf{S}$ of ordinals $\sigma(\beta)$, where $\beta$ may be an arbitrarily large ordinal?" I don't see any reason why we can't do this. To see this the following simple observation would suffice. Whenever arbitrarily large ordinals in $\mathrm{Ord}$ aren't marked as $1$ in an oracle tape we are guaranteed that we can take the supremum of stabilization times above all the $1$'s on the oracle tape (on the very least). This is also why the values $\sigma(\alpha)$ would be strictly increasing w.r.t. ordinal $\alpha$. $\endgroup$
    – SSequence
    Commented Jul 12, 2022 at 7:20
  • $\begingroup$ Also, I think it is probably reasonable to mention (very briefly) that you are talking about stabilization times with respect to first $\omega$ cells. $\endgroup$
    – SSequence
    Commented Jul 12, 2022 at 7:23

0

You must log in to answer this question.