Timeline for What are some interesting applications/corollaries of Kleene's Recursion theorem?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 5, 2023 at 21:09 | comment | added | H.C Manu | This result sounds very counterintuitive which makes it all the more interesting, thanks for sharing. | |
| Jan 5, 2023 at 20:01 | comment | added | Wojowu | @NoahSchweber Very interesting! Thanks for sharing. | |
| Jan 5, 2023 at 19:20 | comment | added | Noah Schweber | @Wojowu It is indeed delightful. Incidentally, it is currently wide open whether there is a linear order whose spectrum (= set of oracles computing copies of it) is exactly the noncomputable degrees; I believe the current best positive result (due to R. Miller) is that there is a linear order $L$ whose spectrum restricted to the degrees below ${\bf 0'}$ is the non-computable degrees. And Greenberg/Montalban/Slaman showed that SW fails for relative constructibility (under an appropriate non-triviality assumption). | |
| Jan 5, 2023 at 18:56 | comment | added | Wojowu | Wow, I have never heard of this result before! I find this surprising given the corresponding result is very much false for sets which are computed by all non-computable oracles, or even almost all (or even all oracles in some given set of positive measure). | |
| Jan 5, 2023 at 18:16 | history | answered | Dan Turetsky | CC BY-SA 4.0 |