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
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 12, 2021 at 9:49 | history | edited | SSequence | CC BY-SA 4.0 |
added 31 characters in body
|
| Apr 12, 2021 at 9:09 | history | edited | SSequence | CC BY-SA 4.0 |
added 29 characters in body
|
| Apr 12, 2021 at 8:52 | history | edited | SSequence | CC BY-SA 4.0 |
deleted 1 character in body
|
| Apr 12, 2021 at 8:45 | history | edited | SSequence | CC BY-SA 4.0 |
deleted 1 character in body
|
| Apr 12, 2021 at 8:39 | history | edited | SSequence | CC BY-SA 4.0 |
added 2988 characters in body
|
| Apr 12, 2021 at 3:12 | comment | added | SSequence | @DmytroTaranovsky Thanks, that's good to know. Actually, I was wondering about this part (and it didn't seem unreasonable that this ordinal $\tau$ in OP might just equal $\eta_0$). One other interesting thing is that while the original question defined the function $f$ and the corresponding ordinal $\tau$ w.r.t. ITTMs, $\eta_0$ still seemed to be upper-bound w.r.t. more general models such as OTMs. (it seems you have mentioned something similar in the first paragraph of your answer, but that's just guess on my part. Perhaps you might have meant something else) | |
| Apr 11, 2021 at 21:39 | comment | added | Dmytro Taranovsky | Your upper bound is actually the exact answer, even if $V≠L$ (see my answer; also, note that $η_0=η$ if $0^\#$ exists). | |
| Apr 10, 2021 at 8:28 | comment | added | SSequence | To put it succinctly, for part-(1), if we think of $r_1$ as encoding a set $B \subseteq \mathbb{N}$ (general case), then it seems that we can divide into following sub-cases: (i) $B \subset A$ (ii) $B=A$ (iii) $B \not \subseteq A$. | |
| Apr 9, 2021 at 2:47 | comment | added | SSequence | Regarding (posting in comment to avoid too many edits): "If $r_2$ represents a linear-order (on $\mathbb{N}$) and we run-out of the initial well-founded segment earlier than $C$ then it isn't a problem. We can just make our program run forever in that case or halt immediately (both choices would seem to work OK)." I think I glossed this over in the initial reply, halting may not be a good idea. We would probably always want to loop forever when we run out of the initial well-founded segment of $r_2$. That would be to account for the case when $r_1$ encodes a strict super-set of $A$. | |
| Apr 9, 2021 at 2:04 | vote | accept | lyrically wicked | ||
| Apr 8, 2021 at 17:37 | comment | added | SSequence | $H_e(r)$ is the halting time of ITTM of index $e$ when given a real $r$. If the ITTM runs forever on some given real $a$, then $H_e(a)=0$. | |
| Apr 8, 2021 at 17:30 | history | edited | SSequence | CC BY-SA 4.0 |
added 44 characters in body
|
| Apr 8, 2021 at 17:23 | history | edited | SSequence | CC BY-SA 4.0 |
added 44 characters in body
|
| Apr 8, 2021 at 17:18 | history | edited | SSequence | CC BY-SA 4.0 |
added 44 characters in body
|
| Apr 8, 2021 at 17:12 | history | edited | SSequence | CC BY-SA 4.0 |
added 44 characters in body
|
| Apr 8, 2021 at 17:05 | history | answered | SSequence | CC BY-SA 4.0 |