A Semitechnical Interlude on the Equivalence of Probabilistic and Deterministic Solomonoff Induction

ASHLEY: Did you say something earlier about the deterministic and probabilistic versions of Solomonoff induction giving the same answers? Like, is it a distinction without a difference whether we ask about simple programs that reproduce the observed data versus simple programs that assign high probability to the data? I can't see why that should be true, especially since Turing machines don't include a randomness source. BLAINE: I'm told the answers are the same but I confess I can't quite see why, unless there's some added assumption I'm missing. They are indeed exactly equivalent, without any need for randomness, but it's a slightly less intuitive formulation. So let's talk about programs that assign probabilities for now, because I think that case is clearer. The above exchange is an alternate ending to section iii of Eliezer Yudkowsky's Semitechnical Introductory Dialogue on Solomonoff Induction, in which a computer scientist named Ashley learns about Solomonoff Induction (the optimal way to predict any sequence with unlimited computing power) from Blaine, who considers it a kind of solution to epistemology itself but doesn't understand why its probabilistic and deterministic versions are equivalent — that is, why it makes no difference whether you consider all programs that print the observed sequence or all programs that predict it. In a separate partition of the space of possible dialogues, Blaine does understand why these two versions are exactly identical, and this scene takes place between section iv and section v. (If you're unfamiliar with Solomonoff Induction or the original dialogue, I suggest reading the original at least up to section iv first.) iv. (a) Probability and Determinism ASHLEY: So, now that you've explained how hypotheses work in Solomonoff induction, it seems like it's completely impossible for it to operate in a deterministic way like I was imagining before. I guess you could think of a program that just prints a sequence of bits as a probabilistic hypothesis that just happens to assign 100% of its probability mass to a single sequence, but in that case we've reduced the probabilistic version's hypotheses down to a strict subset, all of which can only be updated by being zeroed out completely as soon as they get a single symbol wrong. BLAINE: There's certainly a sense in which that's correct, yes. ASHLEY: That would mean that by widening the class of hypotheses to include probabilistic reasoning—an absolutely necessary component of any sensible epistemology, though hardly sufficient—Solomonoff induction becomes no more powerful at all. And this somehow proves that the deterministic version was optimal to begin with. BLAINE: Yes! They're not just equally powerful, they're exactly equivalent. There's no hypothesis that the probabilistic version considers that the deterministic version doesn't account for. ASHLEY: I just can't see that working. Take the fair coin hypothesis. The probabilistic version is easy to imagine: there's some code for it on the universal Turing machine, let's say it's 1001. Once that program is selected, it reads every bit of data and assigns it a probability of mjx-container[jax="CHTML"] { line-height: 0; } mjx-container [space="1"] { margin-left: .111em; } mjx-container [space="2"] { margin-left: .167em; } mjx-container [space="3"] { margin-left: .222em; } mjx-container [space="4"] { margin-left: .278em; } mjx-container [space="5"] { margin-left: .333em; } mjx-container [rspace="1"] { margin-right: .111em; } mjx-container [rspace="2"] { margin-right: .167em; } mjx-container [rspace="3"] { margin-right: .222em; } mjx-container [rspace="4"] { margin-right: .278em; } mjx-container [rspace="5"] { margin-right: .333em; } mjx-container [size="s"] { font-size: 70.7%; } mjx-container [size="ss"] { font-size: 50%; } mjx-container [size="Tn"] { font-size: 60%; } mjx-container [size="sm"] { font-size: 85%; } mjx-container [size="lg"] { font-size: 120%; } mjx-container [size="Lg"] { font-size: 144%; } mjx-container [size="LG"] { font-size: 173%; } mjx-container [size="hg"] { font-size: 207%; } mjx-container [size="HG"] { font-size: 249%; } mjx-container [width="full"] { width: 100%; } mjx-box { display: inline-block; } mjx-block { display: block; } mjx-itable { display: inline-table; } mjx-row { display: table-row; } mjx-row > * { display: table-cell; } mjx-mtext { display: inline-block; } mjx-mstyle { display: inline-block; } mjx-merror { display: inline-block; color: red; background-color: yellow; } mjx-mphantom { visibility: hidden; } _::-webkit-full-page-media, _:future, :root mjx-container { will-change: opacity; } mjx-math { display: inline-block; text-align: left; line-height: 0; text-indent: 0; font-style: normal; font-weight: normal; font-size: 100%; font-size-adjust: none; letter-spacing: normal; border-collapse: collapse; word-wrap: no