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
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2021 at 7:59 | history | edited | lyrically wicked | CC BY-SA 4.0 |
deleted 131 characters in body
|
| Sep 27, 2021 at 4:25 | history | edited | lyrically wicked | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Sep 27, 2021 at 4:10 | vote | accept | lyrically wicked | ||
| Sep 27, 2021 at 3:52 | history | edited | lyrically wicked | CC BY-SA 4.0 |
deleted 1237 characters in body
|
| Sep 26, 2021 at 3:25 | answer | added | Dmytro Taranovsky | timeline score: 3 | |
| Sep 26, 2021 at 3:25 | comment | added | Dmytro Taranovsky | I think you should streamline the question: Instead of oracle input and output tapes, we can have a single binary oracle tape $t$ with $t[α]=1$ iff $α$ is a cardinal. | |
| Sep 25, 2021 at 15:59 | comment | added | SSequence | I am afraid I don't understand what you are saying. I don't know about lost melodies or $0^\#$, so I can't comment on it. Perhaps someone else can clarify. | |
| Sep 25, 2021 at 13:51 | comment | added | lyrically wicked | @SSequence: Regarding $V=L$, doesn't it contradict the existence of zero sharp? But initial ordinals can be used here: see Theorem 27 in this paper. Actually, I do not know how $V=L$ fits the idea of $\omega_{\alpha}$-machines. | |
| Sep 25, 2021 at 13:38 | comment | added | SSequence | $\eta$ is countable. So if we consider the case $\epsilon<\eta$, then $\epsilon$ would be countable too. If we consider the case $\epsilon \geq \eta$, then $\epsilon$ may or may not be countable . I also assumed V=L in all of the comments above (which I forgot to mention, but should have mentioned in my last comment). | |
| Sep 25, 2021 at 13:20 | comment | added | lyrically wicked | @SSequence: when you wrote "$\epsilon \ge \eta$", did you imply that $\epsilon$ was countable (i.e. less than $\omega_1$)? | |
| Sep 25, 2021 at 13:14 | comment | added | SSequence | Brief note: All my comments above about equivalence of sup of $\epsilon$-stabilisation times for both $C_1$ and $C_2$ have been for $0< \epsilon < \eta$. It seems that for $\epsilon \geq \eta$, the situation can (potentially) get more nuanced (so it would need more thought). | |
| Sep 25, 2021 at 12:46 | comment | added | SSequence | But still I haven't read what you wrote in detail, so I won't try to guess things tentatively (also what I have written, I haven't double-checked it in a more careful way). Regarding your second comment, I don't understand what you wrote (nevermind about it though). | |
| Sep 25, 2021 at 12:43 | comment | added | SSequence | OK I guess I will have to read that part bit more carefully. I will perhaps read it in detail later if I get the time to do so. Nevertheless, I will mention that (with V=L), the kind of command you mentioned (in second-last comment) will still have no effect on sup of stabilization times. Unless you do something radically different, being able to test whether a given ordinal $\alpha$ is a cardinal (i.e. of the form $\omega_i$) is likely to be sufficient to emulate what you seem to be doing. However, such an extra command doesn't make a difference to sup of stabilization times. (continued) | |
| Sep 25, 2021 at 12:42 | comment | added | lyrically wicked | @SSequence: Regarding $V=L$ and $\omega_1^L$, this question implies that $\omega_1^L$ (the supremum of ordinals accidentally writable by ordinary OTMs starting with empty input) is countable, so $\omega_1^L$ is less than $\omega_1=\omega_1^V$. [2/2] | |
| Sep 25, 2021 at 12:14 | comment | added | lyrically wicked | @SSequence: Yes, the supremum of stabilization times for the first $\omega$ cells does not seem to make a big difference with the model of ordinary OTMs. This is what I realized soon after posting this question, and this is why I changed the definition of $\tau_0$. Regarding the oracle, it is not only for finding fixed points, it can be used to construct various sets of ordinal parameters. For example, mark the first $\omega$ cells with ones, use the ASK state, and all cells indexed by any element of the set $\{\omega_1, \omega_2, \omega_3, \ldots \}$ will be marked with 1 immediately. [1/2] | |
| Sep 25, 2021 at 11:02 | comment | added | SSequence | Here is one point that, unless I am missing something, follows relatively easily (I think). Let $\eta<\omega^L_1$ denote the sup of eventually writeable ordinals for $C_1$. If we have V=L and $0<\epsilon<\eta$ then supremum of $\epsilon$-stabilization times for both $C_1$ and $C_2$ will be $\mathcal{S}$. | |
| Sep 25, 2021 at 10:32 | comment | added | SSequence | I didn't read the question in detail (so I may have misunderstood). Here is my guess as to what your modified computational does. It can check for the truth/falsity of $\omega_{\alpha}=\alpha$? In what follows, I assume this to be case. Let $C_1$ denote the computational model for ordinary OTMs. Let $C_2$ be the computational model described by you where we have an extra oracle command to check $\omega_{\alpha}=\alpha$. Now we also assume that all programs start from blank tape. For reference, let $\mathcal{S}$ denote the supremum of stabilization times for first $\omega$ cells of $C_1$. | |
| Sep 24, 2021 at 4:20 | history | edited | lyrically wicked | CC BY-SA 4.0 |
deleted 60 characters in body
|
| Sep 24, 2021 at 3:52 | history | edited | lyrically wicked | CC BY-SA 4.0 |
added 100 characters in body
|
| Sep 23, 2021 at 9:26 | history | edited | lyrically wicked | CC BY-SA 4.0 |
added 560 characters in body
|
| Sep 23, 2021 at 9:01 | history | edited | lyrically wicked | CC BY-SA 4.0 |
added 186 characters in body
|
| Sep 23, 2021 at 8:21 | history | edited | lyrically wicked | CC BY-SA 4.0 |
deleted 26 characters in body
|
| Sep 23, 2021 at 8:10 | history | edited | lyrically wicked | CC BY-SA 4.0 |
added 152 characters in body
|
| Sep 23, 2021 at 8:01 | history | edited | lyrically wicked | CC BY-SA 4.0 |
added 553 characters in body
|
| Sep 23, 2021 at 7:32 | history | edited | lyrically wicked | CC BY-SA 4.0 |
added 86 characters in body
|
| Sep 23, 2021 at 5:28 | history | asked | lyrically wicked | CC BY-SA 4.0 |