Timeline for Can a stochastic Turing machine output a consistent extension of PA with positive probability?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 21, 2015 at 19:19 | comment | added | Denis Hirschfeldt | @Andreas Blass I think this is a slightly tricky theorem to credit. The paper you cite proves that if a set is c.e. relative to every real in a class of positive measure, then it is c.e. Of course, the analogous result for computable in place of c.e. is a one-line corollary, but I believe it was never stated in that paper. Later Sacks stated it explicitly and proved it, with essentially the same argument, though as far as I know without knowledge of the earlier paper. | |
| Nov 21, 2015 at 15:06 | comment | added | Carl Mummert | Thanks, Andreas. I had somehow learned the theorem as just due to Sacks. Fortunately Downey and Hirschfeldt state both versions. | |
| Nov 21, 2015 at 15:05 | history | edited | Carl Mummert | CC BY-SA 3.0 |
added 208 characters in body
|
| Nov 21, 2015 at 11:13 | comment | added | Andreas Blass | The fact that, if a real is computable from every real in a set of positive measure, then it's computable is, as far as I know, proved, though with rather different teminology, in the paper (citation opied from MathSciNet): de Leeuw, K.; Moore, E. F.; Shannon, C. E.; Shapiro, N. Computability by probabilistic machines. Automata studies, pp. 183–212. Annals of mathematics studies, no. 34. Princeton University Press, Princeton, N. J., 1956. | |
| Nov 21, 2015 at 0:12 | vote | accept | Abram Demski | ||
| Nov 21, 2015 at 0:29 | |||||
| Nov 21, 2015 at 0:09 | history | edited | Carl Mummert | CC BY-SA 3.0 |
edited body
|
| Nov 20, 2015 at 23:59 | history | answered | Carl Mummert | CC BY-SA 3.0 |