Timeline for Are ITTM's necessary to compute Turing's "computable numbers" and what does that mean for ordinary recursion theory?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 7, 2021 at 21:28 | comment | added | Noah Schweber | and so in particular hyperarithmetic (which I think most people would still consider within the sphere of classical computability theory). And I wouldn't even start thinking about ITTMs at that point, either; at a glance, I wouldn't expect ITTMs to become particularly relevant until around the first $\Sigma_2$-admissible ordinal (which is gigantic), although I'm not an expert. | |
| Jun 7, 2021 at 21:20 | comment | added | Noah Schweber | @ThomasBenjamin I wouldn't say so: figuring out what happens at stage $\omega$ in an ITTM calculation is only a $\Pi^0_2$ question. That is, the tape configuration of an ITTM at stage $\omega$ on input sequence $s$ is uniformly $\Pi^0_2$ relative to $s$. Turing-degree-wise this is only ${\bf 0''}$. As Joel said in the last paragraph of his answer, ITTMs really only enter the picture in a serious way at much larger ordinals. In particular, the tape configuration at stage $\beta<\omega_1^{CK}$ on input sequence $s$ is uniformly $\Pi^0_\beta$ relative to $s$ (and for many $\beta$s much better), | |
| Jun 7, 2021 at 21:00 | comment | added | Thomas Benjamin | *classical computability | |
| Jun 2, 2021 at 21:19 | comment | added | Thomas Benjamin | Thank you also for your very nice answer. A question regarding the "ITTM-stage-$\omega$ characterization of classical computability" : If the $n$th cell on the work tape does not stop changing after stage $k$ but stops changing at stage $\omega$, can it be said that one has left "classical computably"? | |
| May 28, 2021 at 19:25 | history | answered | Noah Schweber | CC BY-SA 4.0 |