Logical predictors cannot dominate their own complexity class

post by Scott Garrabrant · 2015-10-05T04:45:49.000Z · LW · GW · 0 comments

One good property for a logical predictor (A Turing machine which tries to guess the output of an environment $E$ that is too complex to simulate) is that it is able to to do asymptotically at least as well as any other logical predictor in some class.

We say that a logical predictor $L$ dominates all the logical predictors in a set $S$ if for every $s$ in $S$, we get $P(s,E,n)\in O\left(P\right(L,E,n\left)\right),$ where $P(x,E,n)$ is the probability that $x$ and $E$ agree on the first $n$ bits. That is to say that the probability $L$ assigns to the correct environment is at least a constant times the probability that $s$ assigns the correct environment is the limit.

Theorem: It is not in general possible for a machine $L$ which runs in $O\left(f\right(n\left)\right)$ time to dominate the class of all functions which run in $O\left(f\right(n\left)\right)$.

Proof: Consider an environment $E$ which flips pseudorandom coins for its output, such that the $n$th bit output by $E$ could be computed it time $2^{n}g\left(n\right)$, where $g\left(n\right)$ is the number of times $2$ divides $n$. Given less than this amount of time, there is no way to predict the coin flips that does asymptotically better than random.

Let $L$ be a Turing machine which outputs the $n$th bit in $c\cdot 2^n$ time. Consider the set of all $n$ with $g\left(n\right)>c$. $L$ can do no better than random guessing, and so can get the first $k$ such bits correct with probability at most $2^{-k}$. However, there exists a Turing machine which runs in time $O\left(2^n\right),$ and computes the correct answer for all $n$ with $g\left(n\right)\le c+1$, and guess randomly on the rest. This algorithm does is twice as likely on average to get each $n$ with $g\left(n\right)=c+1$. Therefore, the probability that this algorithm gets the first $k$ elements correct divided by the probability that $L$ gets the first $k$ elements correct must go to infinity.

In principle, it is still possible for a logical predictor that runs in time $f\left(n\right)$ to dominate any logical predictor that runs in time $g\left(n\right)$, where $f$ and $g$ are any functions with $g\in o\left(f\right)$. I am working on trying to find a predictor with this property.

0 comments

Comments sorted by top scores.