[millstone]

Question about this paragraph:

> Is it possible to define a process that Solomonoff induction cannot predict? The short answer is yes, but the kinds of computers needed to simulate these processes don’t exist in the real world, and it’s unlikely that we’ll ever be able to build them.

Doesn't "pick a truly random number" qualify? And we can build those today.

[ad510]

When I wrote "predict" there, I was referring to whether the predicted probabilities approach the true underlying probabilities, and Solomonoff induction can "predict" a true random number generator in that sense because its predicted probabilities will approach those of the random number generator. [1] However, if you tried to use it to predict a halting oracle, the halting oracle would be deterministic but Solomonoff induction would never be able to predict it with complete confidence, and this is what I was referring to in that paragraph.

But you're right that random numbers are inherently unpredictable; maybe I should add another footnote explaining what I meant there. (Edit: I added a clarification to the paragraph you quoted.)

[1] http://twistedoakstudios.com/blog/Post5623_solomonoffs-mad-s... in the "Thinking with Programs: Random Data" section

[goldenkey]

One of the principles of turing machines is that they are deterministic. In that vain, there exists no programmable RNG except for pseudo random ones. One has to ask oneself if piping a transform of the digits of a transcendental real number is a violation to this rule -- thus what is random really? Is random the lack of ability to find a correlation or program to reproduce it -- or is it something more like Komogrolov complexity? These are tough and inscrutable questions. Shannon, Turing, Curry, Church, Post, and others explored them deeply. Information theory gets extremely existential and esoteric. Is randomness a monad of our universe? Or is physicals and natural chaos just extremely leathery when it comes to extracting the generating program? Our lives depend on it. But either way, we'll carry on. Nature you goddamn enigma.

[Strilanc]

If you feed biased random bits into Solomonoff induction, the shortest surviving programs at any given point would tend to be things like arithmetic encoders that match the bias and specify just a bit more output. (Assuming you're not using pseudo-random numbers, of course.) So it will at least start to predict probabilities with the correct bias.

If you're feeding in unbiased independent random bits, any and every process is already an optimal predictor.