In this post, I ask two questions about Solomonoff Induction. I am not sure if these questions are open or not. If you know the answer to either of them, please let me know. I think that the answers may be very relevant to stuff I am currently working on in Asymptotic Logical Uncertainty.
Consider a universal Turing machine U which takes in an infinite stream of random bits, and outputs a finite or infinite string of bits. For any bit string w, let P(w) denote the probability that w is a prefix of the output of U.
Let E be an probabilistic environment which outputs an infinite bit string, and set ei be the first i bits output by E.
If E assigns outputs according to any computable probability distribution, then with probability 1, P(ei1)/P(ei) quickly converges to the actual probability that E outputs a 1 at location i+1 given that its first i bits were ei.
In particular, if E outputs an infinite stream of iid bits which are each 1 with some rational probability p, then P(ei1)/P(ei) will converge to p with probability 1.
However I am curious what happens if E is not computable. In the simplest case E outputs an infinite stream of iid bits which are each 1 with some uncomputable real number probability r. In this case, will P(ei1)/P(ei) converge to r with probability 1?
To make things slightly more complicated, assume that the odd index bits of E come from a fair coin, but the even bits come from an adversary who chooses the bits in an uncomputable way. (This adversary can see all the bits output by E so far, but not future bits.) In this case, will P(e2i1)/P(e2i) converge to 1/2?
Two Questions about Solomonoff Induction
In this post, I ask two questions about Solomonoff Induction. I am not sure if these questions are open or not. If you know the answer to either of them, please let me know. I think that the answers may be very relevant to stuff I am currently working on in Asymptotic Logical Uncertainty.
Consider a universal Turing machine U which takes in an infinite stream of random bits, and outputs a finite or infinite string of bits. For any bit string w, let P(w) denote the probability that w is a prefix of the output of U.
Let E be an probabilistic environment which outputs an infinite bit string, and set ei be the first i bits output by E.
If E assigns outputs according to any computable probability distribution, then with probability 1, P(ei1)/P(ei) quickly converges to the actual probability that E outputs a 1 at location i+1 given that its first i bits were ei.
In particular, if E outputs an infinite stream of iid bits which are each 1 with some rational probability p, then P(ei1)/P(ei) will converge to p with probability 1.
However I am curious what happens if E is not computable. In the simplest case E outputs an infinite stream of iid bits which are each 1 with some uncomputable real number probability r. In this case, will P(ei1)/P(ei) converge to r with probability 1?
To make things slightly more complicated, assume that the odd index bits of E come from a fair coin, but the even bits come from an adversary who chooses the bits in an uncomputable way. (This adversary can see all the bits output by E so far, but not future bits.) In this case, will P(e2i1)/P(e2i) converge to 1/2?