Timeline for answer to Can randomness add computability? by Joseph O'Rourke
Current License: CC BY-SA 2.5
Post Revisions
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Mar 10, 2011 at 13:42 | comment | added | Andreas Blass | I believe that the result "randomness doesn't help computability" goes back to a 1956 paper, "Computability by probabilistic machines" by K. de Leeuw, E.F. Moore, C.E. Shannon, and N. Shapiro [in "Automata Studies" Princeton Univ. Press, pp. 183-212]. In modern set-theoretic terminology, the result can be phrased as "any ground model real that is recursive relative to a random (over that ground model) real is in fact recursive." | |
| Mar 10, 2011 at 13:14 | vote | accept | David Harris | ||
| Mar 10, 2011 at 12:58 | history | edited | Joseph O'Rourke | CC BY-SA 2.5 |
added 17 characters in body
|
| Mar 10, 2011 at 12:51 | history | answered | Joseph O'Rourke | CC BY-SA 2.5 |