For instance, there is no computable predictor which always learns to do as well as every other computable predictor on all sequences.
What’s going on here is quite interesting. For any number N, a version of AIXI with time and length bound N is in some sense optimal for it’s compute.
So (in the limit), what you want is a really big N.
One way to do that is to pick a probability distribution over Turing machines, then store Chaitin’s constant ( p(halt) ) to some number of digits. Start running more and more Turing machines for longer and longer until that many halt, and the time taken is your number.
If we take this probability distribution over Turing machines as our prior, then the Turing machines that this algorithm does badly on are the ones that don’t halt in time N. And each extra digit of Chaitin’s constant, on average, halves the measure of such Turing machines.
That’s an interesting way of putting it, though it really has more to do with Solomonoff induction than AIXI, and isn’t really related to AIXI-tl which uses proof search.
What’s going on here is quite interesting. For any number N, a version of AIXI with time and length bound N is in some sense optimal for it’s compute.
So (in the limit), what you want is a really big N.
One way to do that is to pick a probability distribution over Turing machines, then store Chaitin’s constant ( p(halt) ) to some number of digits. Start running more and more Turing machines for longer and longer until that many halt, and the time taken is your number.
If we take this probability distribution over Turing machines as our prior, then the Turing machines that this algorithm does badly on are the ones that don’t halt in time N. And each extra digit of Chaitin’s constant, on average, halves the measure of such Turing machines.
That’s an interesting way of putting it, though it really has more to do with Solomonoff induction than AIXI, and isn’t really related to AIXI-tl which uses proof search.
Yes. Sorry wrong words. I was more meaning Solomonov induction here.