Timeline for Can randomness add computability?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 27, 2023 at 15:39 | comment | added | Gro-Tsen | The answers to this question are quite satisfactory, but don't really provide citable references. “Fact ①” from this other question on CSTheory StackExchange provides a few for the fact that “if $L$ is computable by a non-measure-zero set of oracles, then it is computable”: Sacks, Degrees of Unsolvability (1963), §10, theorem 1 (p. 154); Nies, Computability and Randomness (2009), theorem 5.1.12 (p. 169); or Downey & Hirschfeldt, Algorithmic Randomness and Complexity (2010), corollary 8.2.12 (p. 358). | |
| Jun 12, 2013 at 6:45 | answer | added | none | timeline score: 1 | |
| Mar 10, 2011 at 15:34 | comment | added | Carl Mummert | The program that enumerates every string generates strings of arbitrarily high Kolmogorov complexity. | |
| Mar 10, 2011 at 15:05 | comment | added | Lucas K. | Note that a non-deterministic machine, doesn't extend computability. From this, it is hard to believe that randomness can. | |
| Mar 10, 2011 at 13:14 | vote | accept | David Harris | ||
| Mar 10, 2011 at 12:51 | answer | added | Joseph O'Rourke | timeline score: 20 | |
| Mar 10, 2011 at 11:50 | history | asked | David Harris | CC BY-SA 2.5 |