It's true that a given small seed can generate a long sequence. Sequences like these have low http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikip

It's true that a given small seed can generate a long sequence. Sequences like these have low http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity, since it's possible to write a short program that generates the comparatively long sequence. A pseudo-random number generator with a seed length of 64 bits is capable of generating about 2^64 possible sequences (roughly one for each possible seed). Given a random long sequence, though, it's quite unlikely that there's a short seed that will generate it; given a seed size of 64 bits and a random sequence of 100 bits, for example, the chance that there's a seed that will generate the sequence is roughly (2^64)/(2^100), or about 1 in 100 billion. A theoretically optimal solution to Hutter's challenge would somehow notice whenever this happens to be the case, across all possible seeds and all possible sequence-generating functions, and provide the seed and function as the solution! So, no: it wouldn't be cheating. But, it's statistically likely to be impossible.