Timeline for Turing degree of a turing machine with access to an (arbitrary) nonstandard integer
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 19, 2017 at 19:12 | comment | added | Joel David Hamkins | I have updated with a theorem showing that you cannot compute $0''$ this way, since the total functions you can compute with true nonstandard help are exactly those functions with a $\Sigma^0_2$-definable graph. | |
| Jul 19, 2017 at 19:11 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Fixed second argument
|
| Jul 19, 2017 at 18:59 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Fixed second argument
|
| Jul 19, 2017 at 18:44 | comment | added | Joel David Hamkins | I've changed my mind about that---I no longer think you can compute $0''$ this way, and I shall edit. | |
| Jul 19, 2017 at 7:00 | comment | added | Christopher King | How do you compute $0''$? I'm having trouble since 0' machine might try to solve the halting problem for nonstandard machines if it runs infinitely long. | |
| Jul 18, 2017 at 17:57 | comment | added | Noah Schweber | Incidentally, the hyperarithmetic sets are exactly the ones we get: you've given one direction, and the other follows from e.g. the Gandy basis theorem. | |
| Jul 18, 2017 at 10:44 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 1064 characters in body
|
| Jul 18, 2017 at 10:19 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |