Return to Question

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 least ordinal $\gamma_0$ 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 $\gamma > \gamma_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.)

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.)

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” for this question implies the least ordinal $\gamma_0$ 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 $\gamma > \gamma_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 $\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.)

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 least ordinal $\gamma_0$ 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 $\gamma > \gamma_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.)

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

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.

Can we continue the similar logic unboundedly and define the class $\mathsf{S}$ of ordinals $\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.)

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” for this question implies the least ordinal $\gamma_0$ 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 $\gamma > \gamma_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 $\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.)