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)∈O(P(L,E,n)), 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(f(n)) time to dominate the class of all functions which run in O(f(n)).
Proof: Consider an environment E which flips pseudorandom coins for its output, such that the nth bit output by E could be computed it time 2ng(n), where g(n) 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 nth bit in c⋅2n time. Consider the set of all n with g(n)>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(2n), and computes the correct answer for all n with g(n)≤c+1, and guess randomly on the rest. This algorithm does is twice as likely on average to get each n with g(n)=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(n) to dominate any logical predictor that runs in time g(n), where f and g are any functions with g∈o(f). I am working on trying to find a predictor with this property.
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)∈O(P(L,E,n)), 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(f(n)) time to dominate the class of all functions which run in O(f(n)).
Proof: Consider an environment E which flips pseudorandom coins for its output, such that the nth bit output by E could be computed it time 2ng(n), where g(n) 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 nth bit in c⋅2n time. Consider the set of all n with g(n)>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(2n), and computes the correct answer for all n with g(n)≤c+1, and guess randomly on the rest. This algorithm does is twice as likely on average to get each n with g(n)=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(n) to dominate any logical predictor that runs in time g(n), where f and g are any functions with g∈o(f). I am working on trying to find a predictor with this property.