Asymptotic Logical Uncertainty: Concrete Failure of the Solomonoff Approach post by Scott Garrabrant 1463 days ago | Jim Babcock, Abram Demski, Jessica Taylor and Patrick LaVictoire like this | discuss This post is part of the Asymptotic Logical Uncertainty series. In this post, I give a concrete example of how the Solomonoff Induction Inspired Aproach fails to converge to the correct probabilities when predicting the output of a simple Turing machine. Let $$f:\mathbb{N}\rightarrow \{0,1\}$$ be a function such that (for large $$n$$) $$f(n)$$ can be computed in time $$2^n$$, but there is no algorithm that can predict $$f(n)$$ in time less than $$2^n$$ consistently better than a coin which outputs 1 with probability $$1/3$$. Construct a Turing machine $$E$$ as follows: $$E(2k)=f(2k)$$, and $$E(2k+1)=f(2k+1)$$ XOR $$f(10^k)$$. Imagine trying to predict $$E(k)$$ with an algorithm which takes time at most $$k^2$$. If $$k$$ is even, then it is determined by an event indistinguishable in time $$k^2$$ from a $$1/3$$ coin, so the predictor should output 1 or 0 with probability $$1/3$$. If $$k$$ is odd, then we have the XOR of two bits that are indistinguishable from independently 1 with probability $$1/3$$, so the predictor should output 1 with probability $$4/9$$. Therefore, if we let $$T(k)=k^3$$ and $$R(k)=k^2$$, if SIA worked correctly, then we would have that the limit of the probability that $$SIA(E,T,R)$$ outputs 1 on the even bits would be $$1/3$$. However, this is not the case. In particular, the the probability that the $$10^k$$th bit output by $$SIA(E,T,R)$$ is a 1 will not converge to $$1/3$$, but rather switch between $$4/9$$ and $$5/9$$. This is because at the time that a predictor needs to predict $$E(10^k)$$, it will have already outputted a 1 with probability $$4/9$$ for $$E(2k+1)$$, and had enough time to compute $$f(2k+1)$$. Therefore, if $$f(2k+1)=0$$, then any predictor that does make its prediction for $$E(10^k)$$ match its prediction for $$E(2k+1)$$ will contradict itself. The machines that will do well when sampled in $$SIA(E,T,R)$$ will be the ones that output 1 independently with probability 1/3 for all even bits and 1 with probability $$4/9$$ for all odd bits, EXCEPT when predicting a bit in a location that is a power of 10, in which case, it will copy (or negate) a previous bit, and output 1 with probability either $$4/9$$ or $$5/9$$, both of which are greater than the desired $$1/3$$. Further, a machine that gives a 1 with probability of $$1/3$$ on $$E(10^k)$$ for all $$k$$ will have a likelyhood going to 0 relative to the machines which just copy or negate their old answers. Note that the correct probability with which to believe $$E(10^k)=1$$ really is $$1/3$$, not $$4/9$$ or $$5/9$$. The prediction given to $$E(2k+1)$$ was calculated from a state of ignorance about $$f(2n+1)$$, and this prediction should have no effect on the prediction for $$E(10^k)$$.

### NEW DISCUSSION POSTS

[Note: This comment is three
 by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
 by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
 by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
 by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
 by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes