Timeline for How large are the stabilization times of Ordinal Turing Machines with an oracle for the transfinite initial ordinals?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 30, 2021 at 19:01 | comment | added | Dmytro Taranovsky | @lyricallywicked For a specific set as an oracle, OTM behavior is generically absolute. However, large cardinal axioms are needed to ensure that halting (on empty input) does not depend on whether the oracle is $ω_α^V$ or $ω_α^{V[G]}$. | |
| Sep 30, 2021 at 5:22 | comment | added | lyrically wicked | But given the possible non-absoluteness of “$\omega_{\alpha}$-machines”, do we need to make some extra assumptions if we want to say that for any such machine exactly one of the previously described outcomes is possible? Maybe limit the size of $\epsilon$, fix a particular model etc. [2/2] | |
| Sep 30, 2021 at 5:22 | comment | added | lyrically wicked | I need to clarify one fundamental issue because I don't know how to regard non-absoluteness here. Basically, if we consider no-oracle OTMs with no ordinal parameters, then, given any machine $m$ and some (probably not too large) ordinal $\epsilon$, we can assume that exactly one of the following outcomes is possible: (i) the initial output segment of length $\epsilon$ converges to a particular, specific transfinite binary sequence; (ii) the initial output segment of length $\epsilon$ diverges. [1/2] | |
| Sep 28, 2021 at 17:08 | comment | added | SSequence | @DmytroTaranovsky Oh OK, never mind about the last comment. I was thinking about the oracle in terms of uncountable ordinals only. | |
| Sep 28, 2021 at 16:18 | comment | added | Dmytro Taranovsky | @SSequence Natural numbers are also cardinals. | |
| Sep 28, 2021 at 9:30 | comment | added | SSequence | @DmytroTaranovsky Perhaps you made a minor over-sight in your last comment. It seems that what you wrote is for a machine that keeps moving its head to the right unconditionally (forever) and coverts $0$ on every cell to $1$. However, if I haven't misunderstood the description, the machine in second-last comment keeps moving its head to the right unconditionally (forever), but converts $0$ to $1$ for only those cells whose positions are cardinals. In that case, taking $j$ to be the index of the specific machine, we should have $F_{\epsilon}(j)=0 \Leftrightarrow \epsilon <\omega_1$. | |
| Sep 27, 2021 at 14:20 | comment | added | Dmytro Taranovsky | @lyricallywicked As defined in the question, $F_ϵ(j)=0⇔ϵ=0$ here. The output as a whole diverges, though you can also say that it stabilizes with a proper class output. | |
| Sep 27, 2021 at 8:56 | comment | added | lyrically wicked | I need an explanation for one particular situation. Consider a simple machine $M_j$ which does nothing but copy the current symbol of the oracle tape to the output tape, always move to the right and never halt. What is the outcome of this computation? Do we say that machines like this stabilize and $F_{\epsilon}(j)$ is greater than 0? Or, if $F_{\epsilon}(j) = 0$, is this a special type of stabilization with 0-stabilization time equal to 0? Saying that $M_j$ diverges seems problematic because the symbol on each cell converges, so the outcome must be equal to the entire oracle. | |
| Sep 27, 2021 at 4:10 | vote | accept | lyrically wicked | ||
| Sep 27, 2021 at 3:57 | comment | added | lyrically wicked | I added a clarification to the start of the text of the question. | |
| Sep 26, 2021 at 15:15 | comment | added | Dmytro Taranovsky | @SSequence $\mathcal{T}$ does not depend on nonconstructible sets, so in a generic extension of $L$, it is countable iff the ordinal has been collapsed to be countable; it is countable if $0^\#$ exists. | |
| Sep 26, 2021 at 7:38 | comment | added | SSequence | I have a short question. Denote the supremum of $\omega$-stabiIization times (i.e. first $\omega$ cells) for ordinary OTMs as $\mathcal{T}$ (using this symbol instead of $\mathcal{S}$ to avoid it being confused with $S \subset Ord$ you used). Assuming $V=L$ we have $\mathcal{T}>\omega_1$ (or even $\mathcal{T}=\omega_{\mathcal{T}}$ etc). But assuming $V \neq L$ what are the possiblities for relation between $\mathcal{T}$ and $\omega_1$ and is their neat way to describe them (in few lines)? | |
| Sep 26, 2021 at 3:25 | history | answered | Dmytro Taranovsky | CC BY-SA 4.0 |