Timeline for Absolutely algorithmically random infinite sequence
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 23, 2014 at 18:47 | vote | accept | Dan | ||
| Apr 2, 2014 at 7:59 | history | edited | Dan | CC BY-SA 3.0 |
added 85 characters in body
|
| Apr 2, 2014 at 2:05 | comment | added | Denis Hirschfeldt | Constructing an infinite computable sequence of halting programs shows that the Halting Problem is not bi-immune, but that argument doesn't work for Chaitin's constant. | |
| Apr 2, 2014 at 1:59 | answer | added | Denis Hirschfeldt | timeline score: 6 | |
| Apr 2, 2014 at 1:29 | comment | added | 喻 良 | Recursion theory people call what you called as bi-immuness. It contains all the weakly-random and weakly-generic reals. | |
| Apr 1, 2014 at 23:47 | answer | added | Joel David Hamkins | timeline score: 4 | |
| Apr 1, 2014 at 22:41 | comment | added | Gerry Myerson | Knuth gets stuck into the question of ways to define randomness in Section 3.5 of Volume 2 (Seminumerical Algorithms) of The Art Of Computer Programming, though maybe you are already beyond anything Knuth covers there. | |
| Apr 1, 2014 at 22:40 | comment | added | Richard Stanley | Isn't it the case that if we choose $f$ randomly (each value $f(n)$ independent, with probability 1/2 that $f(n)=0$), then the probability is 1 that $f$ is absolutely random? | |
| Apr 1, 2014 at 21:30 | comment | added | Per Alexandersson | Why does not Chaitin's constant work? How do you construct g and h in this case? The n'th bit is given by the parity of the number of programs of size n, that halts, and I see no way to "peek" at a certain subsequence of this... Related: see also en.wikipedia.org/wiki/Chaitin%27s_constant#Super_Omega | |
| Apr 1, 2014 at 21:21 | history | asked | Dan | CC BY-SA 3.0 |