Thanks, this angle looks interesting, and new to me. Could you explain some more how it’s supposed to work? For example, if the input is an infinite stream of numbers and my hypothesis is something like “next number will be 42” or “prime-numbered members will be prime”, should I pad it with infinite additional entropy?
Normally streams are assumed to be finitely long and have symbols from finite set to keep math neat.
Extension to infinitely long streams with finite complexity are conceptually fairly straightforward using trick very similar to non-normalizable Bayesian prior (just like uniform prior over real numbers is well defined even if it sums to infinity so it’s not really probability, or entropy of a molecule when atom locations are unbound continuous variables), but math can get considerably messier.
Finite or not, streams must be countable.
So just select some ordering and for stream-tester T and number N world generator is “i=0; for(w in streams) { if(T(w)) i += 1; if(i == N) { print(w); break; } }”. There are multiple ways to choose iteration order and encoding for N (simplest would be fixed bit size number, but you need more complicated encoding for infinite number of possibilities obviously), but they’re just a constant away from each other, so you can ignore this detail.
Thanks, this angle looks interesting, and new to me. Could you explain some more how it’s supposed to work? For example, if the input is an infinite stream of numbers and my hypothesis is something like “next number will be 42” or “prime-numbered members will be prime”, should I pad it with infinite additional entropy?
Normally streams are assumed to be finitely long and have symbols from finite set to keep math neat.
Extension to infinitely long streams with finite complexity are conceptually fairly straightforward using trick very similar to non-normalizable Bayesian prior (just like uniform prior over real numbers is well defined even if it sums to infinity so it’s not really probability, or entropy of a molecule when atom locations are unbound continuous variables), but math can get considerably messier.
Finite or not, streams must be countable.
So just select some ordering and for stream-tester T and number N world generator is “i=0; for(w in streams) { if(T(w)) i += 1; if(i == N) { print(w); break; } }”. There are multiple ways to choose iteration order and encoding for N (simplest would be fixed bit size number, but you need more complicated encoding for infinite number of possibilities obviously), but they’re just a constant away from each other, so you can ignore this detail.