An elegant program for a bitstring is the shortest program on a universal Turing machine that outputs this bitstring. According to Kolmogorov complexity, the length of the elegant program is independent of the Turing machine implementation.
Solomonoff induction uses the elegant program for a bitstring to predict the next digit. This is a universal prior given the minimal assumption the output is generated by a Turing machine.
We can use this insight to build a machine learning algorithm called a finite Solmonoff learner. The difference between a finite Solomonoff learner and the original Solmonoff induction algorithm is the finite learner does not have access to all elegant programs. There is no algorithm that can generate all the elegant programs, so the elegant programs the finite learner can use must be stored in memory. With a finite amount of memory, there is a limit to the elegant programs that can be stored and consequently used by the finite learner for prediction.
The limit exists because there are a finite number of elegant programs of a certain length L. When the bitstring of 1s becomes long enough, it is not possible for there to be an elegant program representing the bitstring to be of length L or shorter. If L is the amount of memory available, then eventually the elegant programs will all be longer than L, and none will fit in memory.
Now let's assume we have a very long string of 1s, and we remove one digit to make a prediction problem.
As a concrete example, our bitstring is:
We remove a 1 at random:
The learner must figure out the most likely digit to go in the empty spot.
For a given amount of memory we can make the bitstring of 1s long enough that its elegant program cannot fit in memory. In this case, the finite Solomonoff learner will not be able to access the elegant program for the bitstring, and will thus be incapable of predicting the digit that goes in the empty slot.
To continue the example, assume the elegant program that generates the 1s is:
Furthermore, the amount of memory available is 7 bits. Consequently, the 8 bit elegant program cannot be stored in memory, and the finite learner cannot figure out what goes in the empty slot.
On the other hand, regardless of how long the bitstring of 1s becomes, a human will have no problem identifying the missing digit. A human has finite memory and cannot access all elegant programs to make predictions. Despite having the same handicap as a finite learner, the human can outperform the finite learner infinitely often.
Does this demonstrate Solomonoff learning is less powerful than human learning?