Return to Question

This question is based on the assumption that $V \ne L$ and we have $\omega_1^L < \omega_1$ (here $\omega_1^L$ is equal to the supremum of ordinals accidentally writable by no-oracle Ordinal Turing Machines).

Consider Ordinal Turing Machines (called “$\omega_{\alpha}$-machines”) with an oracle that provides access to all transfinite initial ordinals.

Any $\omega_{\alpha}$-machine is an Ordinal Turing Machine equipped with an extra tape (the oracle tape). We may assume that this tape is read-only.

Let $t(\alpha)$ denote the symbol written on an $\alpha$-th cell of the oracle tape. Then $t(\alpha) = 1$ if and only if $\alpha$ is an initial ordinal.

If $\epsilon > 0$, then the $\epsilon$-stabilization time of a machine is the least ordinal $\gamma_0$ such that the values of all symbols written on all cells of the initial segment of length $\epsilon$ of the output tape never change at any time $\gamma > \gamma_0$. If $\epsilon = 0$, then the $\epsilon$-stabilization time of a machine is the least ordinal $\gamma_0$ such that the values of all symbols written on all cells (i.e. cells indexed by any element of the class of all ordinals) of the entire output tape never change at any time $\gamma > \gamma_0$. If a machine halts, then $\gamma_0$ is not greater than the halting time.

Let $F_{\epsilon}(i)$ denote the $\epsilon$-stabilization time of an $i$-th $\omega_{\alpha}$-machine, assuming that all computations start with no ordinal parameters (i.e. empty input). Here we assume that if a corresponding machine diverges (i.e. the values of all symbols written on all cells of the initial output segment of length $\epsilon$, or all cells of the entire output tape if $\epsilon = 0$, do not stabilize), then $F_{\epsilon}(i) = 0$.

Assuming that we have fixed a particular way to encode a countable ordinal by an infinite binary sequence of length $\omega_0=\omega$, the ordinal $\tau_0$ is defined as the supremum of ordinals eventually writable by $\omega_{\alpha}$-machines with empty input on the initial segment of length $\omega_0=\omega$ of the output tape. The reasoning behind this definition of $\tau_0$ is that there may be $\omega_{\alpha}$-machines whose initial output segment of length $\omega$ stabilizes at a time $\ge \omega_1$ (i.e. $F_{\omega}(i) \ge \omega_1$), yet all other output segments are irrelevant: they stabilize at an arbitrarily large time or even diverge. That is, I suppose that there may exist a machine $M_n$ such that, for example, $F_0(n) = 0$, yet $F_{\omega}(n) \ge \omega_1$. In this case, if the eventually stable content on the initial $\omega$-segment of the output tape encodes an ordinal, this countable ordinal is eventually writable by $M_n$.

The ordinal $\tau_1$ is defined as follows: $$\tau_1 = \sup \{F_0(i) : i \in \mathbb{N}\}.$$

Is it possible to estimate how large are $\tau_0$ and $\tau_1$ (at least, give a “reasonably accurate” estimate for the lower/upper bounds)? In particular, is $\tau_0$ larger than the least ordinal $\delta$ such that $L_{\delta} \prec_{\Sigma_3} L_{\omega_1}$ (the latter is mentioned in this comment and this answer on Mathoverflow)?

This question is based on the assumption that $V \ne L$ and we have $\omega_1^L < \omega_1$ (here $\omega_1^L$ is equal to the supremum of ordinals accidentally writable by no-oracle Ordinal Turing Machines).

Consider Ordinal Turing Machines (called “$\omega_{\alpha}$-machines”) with an oracle that provides access to all transfinite initial ordinals.

Any $\omega_{\alpha}$-machine is an Ordinal Turing Machine equipped with an extra tape (the oracle tape). We may assume that this tape is read-only.

Let $t(\alpha)$ denote the symbol written on an $\alpha$-th cell of the oracle tape. Then $t(\alpha) = 1$ if and only if $\alpha$ is an initial ordinal.

If $\epsilon > 0$, then the $\epsilon$-stabilization time of a machine is the successor of $\gamma_0$, where $\gamma_0$ is the least ordinal such that the values of all symbols written on all cells of the initial segment of length $\epsilon$ of the output tape never change at any time $\gamma > \gamma_0$. If $\epsilon = 0$, then the $\epsilon$-stabilization time of a machine is the successor of $\gamma_0$, where $\gamma_0$ is the least ordinal such that the values of all symbols written on all cells (i.e. cells indexed by any element of the class of all ordinals) of the entire output tape never change at any time $\gamma > \gamma_0$. If a machine halts, then $\gamma_0$ is not greater than the halting time. If an ordinal $\gamma_0$ does not exist, then the corresponding $\epsilon$-stabilization time is $0$.

Let $F_{\epsilon}(i)$ denote the $\epsilon$-stabilization time of an $i$-th $\omega_{\alpha}$-machine, assuming that all computations start with no ordinal parameters (i.e. empty input).

Assuming that we have fixed a particular way to encode a countable ordinal by an infinite binary sequence of length $\omega_0=\omega$, the ordinal $\tau_0$ is defined as the supremum of ordinals eventually writable by $\omega_{\alpha}$-machines with empty input on the initial segment of length $\omega_0=\omega$ of the output tape. The reasoning behind this definition of $\tau_0$ is that there may be $\omega_{\alpha}$-machines whose initial output segments of length $\omega$ stabilize at a time $\ge \omega_1$ (i.e. $F_{\omega}(i) \ge \omega_1$), yet all other output segments are irrelevant: they stabilize at an arbitrarily large time or even diverge. That is, I suppose that there may exist a machine $M_n$ such that, for example, $F_0(n) = 0$, yet $F_{\omega}(n) \ge \omega_1$. In this case, if the eventually stable content on the initial $\omega$-segment of the output tape encodes an ordinal, this countable ordinal is eventually writable by $M_n$.

The ordinal $\tau_1$ is defined as follows: $$\tau_1 = \sup \{F_0(i) : i \in \mathbb{N}\}.$$

Is it possible to estimate how large are $\tau_0$ and $\tau_1$ (at least, give a “reasonably accurate” estimate for the lower/upper bounds)? In particular, is $\tau_0$ larger than the least ordinal $\delta$ such that $L_{\delta} \prec_{\Sigma_3} L_{\omega_1}$ (the latter is mentioned in this comment and this answer on Mathoverflow)?

This question is based on the assumption that $V = L$ is rejected and $\omega_1^L < \omega_1$ (here $\omega_1^L$ is equal to the supremum of ordinals accidentally writable by no-oracle Ordinal Turing Machines).

Consider Ordinal Turing Machines (called “$\omega_{\alpha}$-machines”) with an oracle that provides access to all transfinite initial ordinals.

Any $\omega_{\alpha}$-machine is an Ordinal Turing Machine equipped with an extra tape (the oracle tape). We may assume that this tape is read-only.

Let $t(\alpha)$ denote the symbol written on an $\alpha$-th cell of the oracle tape. Then $t(\alpha) = 1$ if and only if $\alpha$ is an initial ordinal.

If $\epsilon > 0$, then the $\epsilon$-stabilization time of a machine is the least ordinal $\gamma_0$ such that the values of all symbols written on all cells of the initial segment of length $\epsilon$ of the output tape never change at any time $\gamma > \gamma_0$. If $\epsilon = 0$, then the $\epsilon$-stabilization time of a machine is the least ordinal $\gamma_0$ such that the values of all symbols written on all cells (i.e. cells indexed by any element of the class of all ordinals) of the entire output tape never change at any time $\gamma > \gamma_0$. If a machine halts, then $\gamma_0$ is not greater than the halting time.

Let $F_{\epsilon}(i)$ denote the $\epsilon$-stabilization time of an $i$-th $\omega_{\alpha}$-machine, assuming that all computations start with no ordinal parameters (i.e. empty input). Here we assume that if a corresponding machine diverges (i.e. the values of all symbols written on all cells of the initial output segment of length $\epsilon$, or all cells of the entire output tape if $\epsilon = 0$, do not stabilize), then $F_{\epsilon}(i) = 0$.

Assuming that we have fixed a particular way to encode a countable ordinal by an infinite binary sequence of length $\omega_0=\omega$, the ordinal $\tau_0$ is defined as the supremum of ordinals eventually writable by $\omega_{\alpha}$-machines with empty input on the initial segment of length $\omega_0=\omega$ of the output tape. The reasoning behind this definition of $\tau_0$ is that there may be $\omega_{\alpha}$-machines whose initial output segment of length $\omega$ stabilizes at a time $\ge \omega_1$ (i.e. $F_{\omega}(i) \ge \omega_1$), yet all other output segments are irrelevant: they stabilize at an arbitrarily large time or even diverge. That is, I suppose that there may exist a machine $M_n$ such that, for example, $F_0(n) = 0$, yet $F_{\omega}(n) \ge \omega_1$. In this case, if the eventually stable content on the initial $\omega$-segment of the output tape encodes an ordinal, this countable ordinal is eventually writable by $M_n$.

The ordinal $\tau_1$ is defined as follows: $$\tau_1 = \sup \{F_0(i) : i \in \mathbb{N}\}.$$

Is it possible to estimate how large are $\tau_0$ and $\tau_1$ (at least, give a “reasonably accurate” estimate for the lower/upper bounds)? In particular, is $\tau_0$ larger than the least ordinal $\delta$ such that $L_{\delta} \prec_{\Sigma_3} L_{\omega_1}$ (the latter is mentioned in this comment and this answer on Mathoverflow)?

This question is based on the assumption that $V \ne L$ and we have $\omega_1^L < \omega_1$ (here $\omega_1^L$ is equal to the supremum of ordinals accidentally writable by no-oracle Ordinal Turing Machines).

Consider Ordinal Turing Machines (called “$\omega_{\alpha}$-machines”) with an oracle that provides access to all transfinite initial ordinals.

Any $\omega_{\alpha}$-machine is an Ordinal Turing Machine equipped with an extra tape (the oracle tape). We may assume that this tape is read-only.

Let $t(\alpha)$ denote the symbol written on an $\alpha$-th cell of the oracle tape. Then $t(\alpha) = 1$ if and only if $\alpha$ is an initial ordinal.

If $\epsilon > 0$, then the $\epsilon$-stabilization time of a machine is the least ordinal $\gamma_0$ such that the values of all symbols written on all cells of the initial segment of length $\epsilon$ of the output tape never change at any time $\gamma > \gamma_0$. If $\epsilon = 0$, then the $\epsilon$-stabilization time of a machine is the least ordinal $\gamma_0$ such that the values of all symbols written on all cells (i.e. cells indexed by any element of the class of all ordinals) of the entire output tape never change at any time $\gamma > \gamma_0$. If a machine halts, then $\gamma_0$ is not greater than the halting time.

Let $F_{\epsilon}(i)$ denote the $\epsilon$-stabilization time of an $i$-th $\omega_{\alpha}$-machine, assuming that all computations start with no ordinal parameters (i.e. empty input). Here we assume that if a corresponding machine diverges (i.e. the values of all symbols written on all cells of the initial output segment of length $\epsilon$, or all cells of the entire output tape if $\epsilon = 0$, do not stabilize), then $F_{\epsilon}(i) = 0$.

Assuming that we have fixed a particular way to encode a countable ordinal by an infinite binary sequence of length $\omega_0=\omega$, the ordinal $\tau_0$ is defined as the supremum of ordinals eventually writable by $\omega_{\alpha}$-machines with empty input on the initial segment of length $\omega_0=\omega$ of the output tape. The reasoning behind this definition of $\tau_0$ is that there may be $\omega_{\alpha}$-machines whose initial output segment of length $\omega$ stabilizes at a time $\ge \omega_1$ (i.e. $F_{\omega}(i) \ge \omega_1$), yet all other output segments are irrelevant: they stabilize at an arbitrarily large time or even diverge. That is, I suppose that there may exist a machine $M_n$ such that, for example, $F_0(n) = 0$, yet $F_{\omega}(n) \ge \omega_1$. In this case, if the eventually stable content on the initial $\omega$-segment of the output tape encodes an ordinal, this countable ordinal is eventually writable by $M_n$.

The ordinal $\tau_1$ is defined as follows: $$\tau_1 = \sup \{F_0(i) : i \in \mathbb{N}\}.$$

Is it possible to estimate how large are $\tau_0$ and $\tau_1$ (at least, give a “reasonably accurate” estimate for the lower/upper bounds)? In particular, is $\tau_0$ larger than the least ordinal $\delta$ such that $L_{\delta} \prec_{\Sigma_3} L_{\omega_1}$ (the latter is mentioned in this comment and this answer on Mathoverflow)?

Consider a model of Ordinal Turing Machines (called “$\omega_{\alpha}$-machines”) with a special oracle that provides a dynamic access to the transfinite initial ordinals.

Any $\omega_{\alpha}$-machine is an Ordinal Turing Machine equipped with two extra tapes, the oracle input tape and the oracle output tape. Additionally (for convenience), the alphabet is extended to four symbols in the set $\{0,1,2,3\}$, instead of the usual $\{0,1\}$.

Let $t(\alpha)$ denote the symbol written on an $\alpha$-th cell of the oracle input tape at the time when a machine goes into the ASK state.

The oracle operates as follows.

If there are no non-zero symbols written on the oracle input tape (that is, $t(\alpha) = 0$ for all $\alpha \in \text{Ord}$), the oracle puts a machine into the NO state and the computation continues. Otherwise, the oracle performs the following five steps in this exact order (obviously, the order of steps here is significant):

1. All non-zero symbols on the oracle output tape are replaced with 0;
2. For any ordinal $\alpha$ such that $t(\alpha) = 1$ and $\omega_{\alpha} \ne \alpha$, a zero symbol on the $\omega_{\alpha}$-th cell of the oracle output tape is replaced with $1$;
3. For any ordinal $\alpha$ such that $t(\alpha) = 1$ and $\omega_{\alpha} = \alpha$, a symbol (either 0 or 1) on the $\omega_{\alpha+1}$-th cell of the oracle output tape is replaced with $2$;
4. Assuming that $T(\alpha)$ denotes the symbol written on an $\alpha$-th cell of the oracle output tape at the time when the result of step 3 is complete, let $\beta = \sup \{\alpha : T(\alpha) \in \{ 1,2 \}\}$. Then a zero symbol on the $\beta$-th cell of the oracle output tape is replaced with $3$;
5. The oracle puts a machine into the YES state and the computation continues.

If $\epsilon > 0$, then the $\epsilon$-stabilization time of a machine is the least ordinal $\gamma_0$ such that the values of all symbols written on all cells of the initial segment of length $\epsilon$ of the output tape (not the oracle output tape) never change at any time $\gamma > \gamma_0$. If $\epsilon = 0$, then the $\epsilon$-stabilization time of a machine is the least ordinal $\gamma_0$ such that the values of all symbols written on all cells (i.e. cells indexed by any element of the class of all ordinals) of the entire output tape (not the oracle output tape) never change at any time $\gamma > \gamma_0$. If a machine halts, then $\gamma_0$ is not greater than the halting time.

Let $F_{\epsilon}(i)$ denote the $\epsilon$-stabilization time of an $i$-th $\omega_{\alpha}$-machine, assuming that all computations start with no ordinal parameters (i.e. empty input). Here we assume that if a corresponding machine diverges (i.e. the values of all symbols written on all cells of the initial output segment of length $\epsilon$, or all cells of the entire output segment if $\epsilon = 0$, do not stabilize), then $F_{\epsilon}(i) = 0$.

Assuming that we have fixed a particular way to encode a countable ordinal by an infinite binary sequence of length $\omega_0=\omega$, the ordinal $\tau_0$ is defined as the supremum of ordinals eventually writable on the initial segment of length $\omega_0=\omega$ of the output tape (not the oracle output tape) by $\omega_{\alpha}$-machines with empty input. The reasoning behind this definition of $\tau_0$ is that there may be $\omega_{\alpha}$-machines whose initial output segment of length $\omega$ stabilizes at a time $\ge \omega_1$ (i.e. $F_{\omega}(i) \ge \omega_1$), yet all other output segments are irrelevant: they stabilize at an arbitrarily large time or even diverge. That is, I suppose that there may exist a machine $M_n$ such that, for example, $F_0(n) = 0$, yet $F_{\omega}(n) \ge \omega_1$. In this case, if the eventually stable content on the initial $\omega$-segment of the output tape encodes an ordinal, this countable ordinal is eventually writable by $M_n$.

This question is based on the assumption that $V = L$ is rejected and $\omega_1^L < \omega_1$ (here $\omega_1^L$ is equal to the supremum of ordinals accidentally writable by no-oracle Ordinal Turing Machines).

Consider Ordinal Turing Machines (called “$\omega_{\alpha}$-machines”) with an oracle that provides access to all transfinite initial ordinals.

Any $\omega_{\alpha}$-machine is an Ordinal Turing Machine equipped with an extra tape (the oracle tape). We may assume that this tape is read-only.

Let $t(\alpha)$ denote the symbol written on an $\alpha$-th cell of the oracle tape. Then $t(\alpha) = 1$ if and only if $\alpha$ is an initial ordinal.

If $\epsilon > 0$, then the $\epsilon$-stabilization time of a machine is the least ordinal $\gamma_0$ such that the values of all symbols written on all cells of the initial segment of length $\epsilon$ of the output tape never change at any time $\gamma > \gamma_0$. If $\epsilon = 0$, then the $\epsilon$-stabilization time of a machine is the least ordinal $\gamma_0$ such that the values of all symbols written on all cells (i.e. cells indexed by any element of the class of all ordinals) of the entire output tape never change at any time $\gamma > \gamma_0$. If a machine halts, then $\gamma_0$ is not greater than the halting time.

Let $F_{\epsilon}(i)$ denote the $\epsilon$-stabilization time of an $i$-th $\omega_{\alpha}$-machine, assuming that all computations start with no ordinal parameters (i.e. empty input). Here we assume that if a corresponding machine diverges (i.e. the values of all symbols written on all cells of the initial output segment of length $\epsilon$, or all cells of the entire output tape if $\epsilon = 0$, do not stabilize), then $F_{\epsilon}(i) = 0$.

Assuming that we have fixed a particular way to encode a countable ordinal by an infinite binary sequence of length $\omega_0=\omega$, the ordinal $\tau_0$ is defined as the supremum of ordinals eventually writable by $\omega_{\alpha}$-machines with empty input on the initial segment of length $\omega_0=\omega$ of the output tape. The reasoning behind this definition of $\tau_0$ is that there may be $\omega_{\alpha}$-machines whose initial output segment of length $\omega$ stabilizes at a time $\ge \omega_1$ (i.e. $F_{\omega}(i) \ge \omega_1$), yet all other output segments are irrelevant: they stabilize at an arbitrarily large time or even diverge. That is, I suppose that there may exist a machine $M_n$ such that, for example, $F_0(n) = 0$, yet $F_{\omega}(n) \ge \omega_1$. In this case, if the eventually stable content on the initial $\omega$-segment of the output tape encodes an ordinal, this countable ordinal is eventually writable by $M_n$.