Timeline for Can a halting oracle determine if a Turing machine is an ordinal?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 8, 2023 at 4:32 | answer | added | Noah Schweber | timeline score: 6 | |
| Aug 30, 2023 at 14:10 | comment | added | Noah Schweber | The first chapter of Sacks' book Higher recursion theory is also a great source on this; both books, incidentally, are freely-and-legally available from projecteuclid. | |
| Aug 30, 2023 at 13:42 | comment | added | Sam Forster | @Gro-Tsen Thank you, I'll check it out. | |
| Aug 30, 2023 at 13:34 | review | Close votes | |||
| Sep 14, 2023 at 3:02 | |||||
| Aug 30, 2023 at 13:28 | comment | added | Gro-Tsen | @SamForster What you denote $\mathcal{O}_k$ represents the Turing degree $\mathbf{0}^{(k)}$, i.e., the $k$-th Turing jump of $\mathbf{0}$. These are all far below Kleene's $\mathscr{O}$, whose degree is $> \mathbf{0}^{(\gamma)}$ for every $\gamma < \omega_1^{CK}$ (the Church-Kleene ordinal). To learn more about all this, I recommend Hinman's book Recursion-Theoretic Hierarchies (1978). | |
| Aug 30, 2023 at 13:20 | comment | added | Sam Forster | @BenedictEastaugh Thank you. Then I guess my question is equivalent to asking if any of the oracles in my question $\mathcal{O}_0, \mathcal{O}_1, \dots$ are strong enough to encode a $\Pi_1^1$-complete set. Is that known? | |
| Aug 30, 2023 at 13:17 | comment | added | Benedict Eastaugh | The set of (indexes of) recursive ordinals, aka Kleene's $\mathcal{O}$, is $\Pi^1_1$-complete, so you would need an oracle for a $\Pi^1_1$-complete set. | |
| Aug 30, 2023 at 13:09 | history | asked | Sam Forster | CC BY-SA 4.0 |