Timeline for How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 9, 2022 at 10:44 | answer | added | CSW | timeline score: 0 | |
| Apr 11, 2021 at 21:25 | answer | added | Dmytro Taranovsky | timeline score: 2 | |
| Apr 9, 2021 at 2:04 | vote | accept | lyrically wicked | ||
| Apr 8, 2021 at 17:27 | comment | added | SSequence | @DanTuretsky I wrote an answer. Sorry if the part-(1) of my answer is too similar to your comment (since I didn't fully understand what you wrote or proved in your first comment). | |
| Apr 8, 2021 at 17:05 | answer | added | SSequence | timeline score: 3 | |
| Apr 8, 2021 at 15:07 | comment | added | SSequence | @lyricallywicked Yes it does.The ordinal is also defined in "definition-3.10 (ii)" in the current version. As I mentioned just above your comment that (on the very least for V=L) it seems one should get $\tau \leq \eta_0$. And since $\eta_0<\eta$, as a rough upper-bound for $\tau$, that seems to imply $\tau<\eta$. | |
| Apr 8, 2021 at 13:46 | comment | added | lyrically wicked | @SSequence: it seems that your interpretation of the definition of $f$ is correct. Question: does "the supremum of eventually writeables" in the comment above matches the ordinal mentioned in Lemma 3.11 (3) in the linked paper? | |
| Apr 8, 2021 at 10:56 | comment | added | SSequence | With regards to second last comment, it seems that a stronger uppper-bound on $\tau$ could be inferred with $\tau \leq \eta_0$ (again taking V=L to be safe). Here $\eta_0$ is the supremum of eventually writeables (e.g. for OTMs) that stabilize in countable time. But two things are: (i) It depends on the interpretation of question being as in last comment (ii) It is just an upper-bound on $\tau$ and not a lower-bound. | |
| Apr 8, 2021 at 10:08 | comment | added | SSequence | @lyricallywicked I have the feeling that this is what you intend? You want to define a function $f:\mathbb{N} \rightarrow \omega_1$ with the following definition for $f(i)$. For a given $i \in \mathbb{N}$, denoting $\alpha_i=\sup\{H_i(x)\,|\,x \in \mathbb{R}\}$, you want to define $f(i)=0$ if $\alpha_i \geq \omega_1$ and $f(i)=\alpha_i$ if $\alpha_i<\omega_1$. The symbol $H_i(x)$ gives the halting time for an ITTM of index $i$ with an input real $x$ (and $0$ if the given ITTM never halts). Is this what you intend in your question? | |
| Apr 8, 2021 at 10:01 | comment | added | SSequence | @DanTuretsky At least under V=L [adding it to be on the safe side as my knowledge of sets is really lacking], upon a quick look it seems that for the ordinal mentioned as $\tau$ should be $\leq \eta$ (supremum of eventually writeables for OTMs). I haven't written it and just thought it mentally though, so I need to re-check it a bit. Also, I am a bit uncertain about the intention of the question. | |
| Apr 8, 2021 at 5:40 | comment | added | Dan Turetsky | It should be greater than $\sigma$ (the least $\Sigma_1$-stable ordinal). You can make a machine that, given a linear order $\alpha$ and a set $X \subseteq \omega$, simulates each OTM in $X$ along the well-founded part of $\alpha$ sequentially, entering an infinite loop if any run beyond the well-founded part. Then its runtime is maximized by giving it $\alpha = \sigma$ and $X$ halting OTMs with runtimes cofinal in $\sigma$. | |
| Apr 8, 2021 at 5:03 | history | edited | lyrically wicked | CC BY-SA 4.0 |
added 13 characters in body
|
| Apr 8, 2021 at 4:55 | history | edited | lyrically wicked | CC BY-SA 4.0 |
edited body
|
| Apr 8, 2021 at 4:22 | history | asked | lyrically wicked | CC BY-SA 4.0 |