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 . A sequence of length n gets , or .
BLAINE: Right. Easy.
ASHLEY: But if I try to imagine the deterministic version, I hit problem number 1 straight away: there are infinitely many sequences we have to be able to print!
BLAINE: Not a problem at all—remember, we're running this on infinitely fast, and infinitely large, computers.
ASHLEY: That handles the runtime, but not the specification. The fair coin hypothesis assigns even probability to every observable sequence, and we have to replace that one simple program with infinitely many replacements that all print different sequences. And if they all receive the same weight—and they have to, that's the whole point of the fair coin hypothesis—then they all get a weight that's divided by infinity, but oops, that's zero. On the face of it, it seems impossible to specify the fair coin hypothesis in the deterministic setting.
BLAINE: How's this for a deterministic specification: on input 1001, wait for more input. Then, print whatever follows!
ASHLEY: Follows what? "1001" is code, specifying a program. And the code is prefix-free, so once it's been specified, it shouldn't be followed by anything else, right?
BLAINE: "1001" is a specification of a program, yes. To a UTM, it's written on a tape that the machine reads—no reason why it can't continue. And if it does, the code being prefix-free means that we can know for certain when the code ends and the input to the program begins.
ASHLEY: That's closer to the original definition of a universal Turing machine, which is just a Turing machine that can emulate any other Turing machine, if given a description of the machine it's supposed to emulate, followed by any input that machine should receive. But that makes it quite different from the one we just had.
BLAINE: Sort of. Partly that's because it has to be—we've switched it from giving probabilities as outputs to giving strings of bits, so it can't be exactly the same machine.
Anyway, with the machine taking input from the same tape we used to specify a program, the two models become exactly equivalent. The probabilistic version receives "1001" and evaluates the data with the fair coin hypothesis. The deterministic version receives "1001" and outputs whatever follows, meaning that it gives equal probability to every symbol at every point, i.e. ! And assigns—
ASHLEY: — a probability of to a sequence of length n, sure, but that breaks your rule from before about prefix-free codes. If I want to predict the data "000" using the fair coin hypothesis, I have to take the weight of the input "1001000". If I want to predict "0000" or "0001", I have to weigh "10010000" and "10010001"—which both have that last input as a prefix!
BLAINE: That's fine in this case—we only need the code for the fair coin hypothesis to be prefix-free compared to other hypotheses. So it's only the "1001" that matters for prefix-freedom, as before. If we condition on that hypothesis, ignoring its code as part of the input, then we have a probability of on "000", each on "0000" and "0001".
ASHLEY: That doesn't solve the problem at all—the string "0" has a probability of , and so does "1"—that already sums to 1. Then we have four two-bit-long strings, each with —another 100%! It's growing every time we add a new character!
BLAINE: That's the same if you consider those separate inputs to the probabilistic fair coin hypothesis, though. The answer to the question "if I flip a fair coin, what's the probability of heads?" is , same for tails. For any particular two-coin sequence, it's . And yet that's not breaking the laws of probability.
ASHLEY: Hmm, I think I sort of see your point. With the coins, every additional flip gives a new sequence with half the probability of the original... still, it doesn't seem quite right that the probability of seeing "000" is the same as seeing "0000" plus seeing "0001". "000" is shorter than either of those—doesn't that make it simpler, and therefore more likely?
BLAINE: Um. Yes? It is more likely. Twice as likely, in fact.
ASHLEY: Twice as much as either one, but it's no more than their sum.
BLAINE: Solomonoff induction's main use, to the degree that it makes sense to speak of using such an uncomputable algorithm, is to take some data and predict what comes next. If you're 3 characters into reading a binary sequence from the beginning and so far you've seen the string "000", the fair coin hypothesis assigns that a chance of happening, and each that you'll see a "0" or a "1" next.
So instead of assigning probabilities to strings of a particular length, the aim is to partition the space of possible strings in a way that assigns probabilities to every string, then splits its probability mass between its continuations.
ASHLEY: Hmm. I suppose so.
Okay, I think I buy that the deterministic and probabilistic setups can be made identical for that one specific hypothesis, since it can just assign uniform probabilities to uniform outputs from uniform inputs. And it's trivial for hypotheses that always assign all of their weight to a single sequence. But I can't see how to generalize that to anything more complex. The fair coin hypothesis is the only one where printing the input directly will work.
BLAINE: The key to the generalization is that each probabilistic hypothesis can be specified on a deterministic UTM, and then that hypothesis' measure over binary strings can be mapped on to the measure of possible inputs.
ASHLEY: But it can't randomly sample from possible inputs to produce a distribution of outputs, can it? Or are we positing that this infinitely large computer came with a free True Randomness module to go with its Halting Oracle?
BLAINE: It doesn't need one—just like probabilistic Solomonoff induction takes the total output of all inputs it could receive, so can this one. Why sample when you can just add up the population?
ASHLEY: Okay, explain to me how it would generalize from coins to sensory inputs to give a weight on some deterministic program that somehow outputs my entire life experience followed by the sight of the headline "CANADA INVADES USA". I'll grant you that that's possible under the probabilistic scheme.
BLAINE: Sure. Let's assume we run probabilistic Solomonoff induction on everything you've ever seen and heard and felt, and we land on some set of hypotheses about ways the world could be that predict your life experience relatively well. Some of those will assign some small probability to the sight of "CANADA INVADES USA", as interpreted from your screen by your brain via your eyes.
ASHLEY: Truly tiny, but sure.
BLAINE: If we assume that you're polite enough not to check your phone within the next few milliseconds, there'll be some stream of sensory input bridging from the current moment to whenever you check that headline—let's say tomorrow morning.
ASHLEY: Right, and I suppose some potential sensory streams will give higher conditional likelihoods, like seeing Canadian warplanes overhead or reading that the President denounced this afternoon's bombing of... let's say Detroit.
BLAINE: Sure. Then there's some finite total number of possible sensory streams that you could have, agreed?
ASHLEY: It doesn't feel finite, but I have to concede it can't be infinite.
BLAINE: Every number that isn't infinity is the same to Solomonoff induction. So we can enumerate every sensory stream you could have from now until you open the news tomorrow, and assign a slice of probability to each one—a slice that no other stream can ever get. So we can slowly map the entire space of things-you-can-experience-from-now-until-tomorrow, then add up the total weight of all the ones that end with the sight of "CANADA INVADES USA".
ASHLEY: Sounds like what you described before, sure.
BLAINE: Here's what the deterministic version does: it can have the exact same hypotheses as the probabilistic version. Then, just like the fair coin hypothesis read its input and output a string that was equally complex, the UTM can keep reading more input after the prefix-free code for any particular hypothesis, and interpret it as a decimal. Erm, but a binary decimal... a binaral? I feel like I should have a word for that...
ASHLEY: I know what you mean. I think it's just called a 'binary fraction'.
BLAINE: That'll do. So we can imagine the input continuing to be a more and more precise binary fraction, so that eventually, no matter how it continues, it specifies a specific slice in our enumeration of all your possible experiences. We then say that the UTM outputs that exact experience on seeing that binary fraction.
(whispering) No, that just doesn't sound right...
ASHLEY: Surely not every input can specify some slice—maybe you can make sure that the prefix-free code is complete, but some inputs won't halt, or won't provably halt.
BLAINE: True, but no more so than in the probabilistic domain—same prefix-free code, same computation, so any non-halting program in one domain is present in the other, with exactly the same measure in both.
ASHLEY: Okay, I think I get what you mean by 'measures' before, and I can see how that would lead to the deterministic form mapping all possible inputs on to all possible outputs in a way that exactly matches the probabilistic form. But that's only a limited output, when we want to predict what's coming next, forever and ever, right?
BLAINE: Right. To predict what you see next—that is, exactly how the war plays out for you—we have to enumerate longer sensory streams that divide the probability space more finely. The probabilistic form would have to do the same thing—predict likelihoods of longer streams, and assign them less weight so they can still all add to 1.
ASHLEY: And we can be sure that outputting a particular experience won't be something we regret later, because the input stream now corresponds to some different output? For example, can we be sure that there isn't some stream where following it with "000" predicts that I'll read "CANADA INVADES USA", but "0001" instead predicts "CANADA AND USA NOT AT WAR, EVERYTHING FINE"?
BLAINE: If the probability assignments were consistent in the probabilistic scheme, then yes, we can be absolutely sure. In both cases, it's impossible for the weight on "0001" and "0000" to exceed the weight on "000", so if we split the space of observed data correctly, we can be sure that our outputs match the probabilistic scheme exactly. Adding the "1" on the end might not fully specify what you see after reading "CANADA INVADES USA", but it can't remove that part of the sequence, it can only add to it.
ASHLEY: Hmm... I guess if the deterministic version is just copying the probabilistic version then it's not worse.
It certainly doesn't seem better, though. What's the point if it's just copying the probabilistic scheme?
BLAINE: No, it's not better, nor is it worse—again, it's exactly identical. The probabilistic scheme stops when it gets an input that specifies a program, and then splits the probability space further according to that program. The deterministic scheme starts when it gets an input that specifies a program, uses that program to interpret further input, and splits the probability space further according to that input. One kind has prefix-free encodings of hypotheses, the other has prefix-free encodings of interpreters. For any UTM that does it one way, you can make another UTM that does it the other way.
ASHLEY: You haven't said anything about the other direction—why would a probabilistic version of any deterministic UTM exist?
BLAINE: That's even easier—you just take every program on the deterministic UTM and see what probabilities it assigns to the sequence. Boom, you've converted it back into a probabilistic hypothesis.
ASHLEY: That requires scanning infinitely many... ah, I need to let go of that instinct. You need to scan every possible input, but that's fine, we have a magic computer.
BLAINE:Hypercomputer is the technical term.
ASHLEY: I know, you said.
So on this magic computer, there's an exact equivalence between programs as probabilistic hypotheses, and programs as deterministic interpreters of the rest of the input that started with the interpreter's encoding.
BLAINE: That's right—a precise, 1-to-1 correspondence. A distinction without a difference, as you put it.
ASHLEY: But you said you preferred the probabilistic version. Why?
BLAINE: Several reasons.
Firstly, I find it more intuitive to think about assigning probabilities than measuring spaces of possible inputs. Human beings don't think about the measure of the space of possible conditions that could feed into the Earth's weather system to make it rain tomorrow, we just think about the chance that it'll rain.
Secondly, I think that updating using Bayes' rule is a better model of epistemology than cancelling programs that output incorrect sequences, even though they describe the same shift in the probability space. In the deterministic version, you just keep checking more and more possible inputs to the UTM. The prior likelihood of a program, the posterior likelihood that that program assigns to a particular sequence, and the continuation of that sequence all come from the same source.
But in real life, assigning priors and evaluating posteriors seem to be distinct skills.
In the probabilistic version, they both receive different terms in the equation, even though they're measured in the same unit. There's value in being able to separate parts of an unbounded model that work differently in real life, even when they don't need to be separated if you have a hypercomputer.
ASHLEY: You do, of course, recognize the irony in preferring a version of Solomonoff induction with additional terms that its counterpart lacks?
BLAINE: Hey, I'm a bounded agent that can benefit from additional complexity, so sue me.
There are also distinctions between assigning priors and generating hypotheses, and between evaluating them against what data you have and extrapolating from them to make predictions, neither of which are separated by either version of Solomonoff induction. But the first one is a result of cheating by simply enumerating all hypotheses, and the second is a result of cheating by enumerating all continuations of the sequence, and I'm not aware of any way to get around those.
Anyway, my third reason for preferring the probabilistic version is that determinism requires your hypotheses to predict the data perfectly, which is rarely attainable in real life, while probabilistic hypotheses can be updated and compared against each other even if the ideal hypothesis hasn't been generated yet.
ASHLEY: That all sounds reasonable.
BLAINE: Fantastic! Does that mean all of your questions are answered and you're now convinced that Solomonoff induction is the optimal unbounded solution to epistemology?
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
BLAINE: Right. Easy.
ASHLEY: But if I try to imagine the deterministic version, I hit problem number 1 straight away: there are infinitely many sequences we have to be able to print!
BLAINE: Not a problem at all—remember, we're running this on infinitely fast, and infinitely large, computers.
ASHLEY: That handles the runtime, but not the specification. The fair coin hypothesis assigns even probability to every observable sequence, and we have to replace that one simple program with infinitely many replacements that all print different sequences. And if they all receive the same weight—and they have to, that's the whole point of the fair coin hypothesis—then they all get a weight that's divided by infinity, but oops, that's zero. On the face of it, it seems impossible to specify the fair coin hypothesis in the deterministic setting.
BLAINE: How's this for a deterministic specification: on input 1001, wait for more input. Then, print whatever follows!
ASHLEY: Follows what? "1001" is code, specifying a program. And the code is prefix-free, so once it's been specified, it shouldn't be followed by anything else, right?
BLAINE: "1001" is a specification of a program, yes. To a UTM, it's written on a tape that the machine reads—no reason why it can't continue. And if it does, the code being prefix-free means that we can know for certain when the code ends and the input to the program begins.
ASHLEY: That's closer to the original definition of a universal Turing machine, which is just a Turing machine that can emulate any other Turing machine, if given a description of the machine it's supposed to emulate, followed by any input that machine should receive. But that makes it quite different from the one we just had.
BLAINE: Sort of. Partly that's because it has to be—we've switched it from giving probabilities as outputs to giving strings of bits, so it can't be exactly the same machine.
Anyway, with the machine taking input from the same tape we used to specify a program, the two models become exactly equivalent. The probabilistic version receives "1001" and evaluates the data with the fair coin hypothesis. The deterministic version receives "1001" and outputs whatever follows, meaning that it gives equal probability to every symbol at every point, i.e.
ASHLEY: — a probability of
BLAINE: That's fine in this case—we only need the code for the fair coin hypothesis to be prefix-free compared to other hypotheses. So it's only the "1001" that matters for prefix-freedom, as before. If we condition on that hypothesis, ignoring its code as part of the input, then we have a probability of
ASHLEY: That doesn't solve the problem at all—the string "0" has a probability of
BLAINE: That's the same if you consider those separate inputs to the probabilistic fair coin hypothesis, though. The answer to the question "if I flip a fair coin, what's the probability of heads?" is
ASHLEY: Hmm, I think I sort of see your point. With the coins, every additional flip gives a new sequence with half the probability of the original... still, it doesn't seem quite right that the probability of seeing "000" is the same as seeing "0000" plus seeing "0001". "000" is shorter than either of those—doesn't that make it simpler, and therefore more likely?
BLAINE: Um. Yes? It is more likely. Twice as likely, in fact.
ASHLEY: Twice as much as either one, but it's no more than their sum.
BLAINE: Solomonoff induction's main use, to the degree that it makes sense to speak of using such an uncomputable algorithm, is to take some data and predict what comes next. If you're 3 characters into reading a binary sequence from the beginning and so far you've seen the string "000", the fair coin hypothesis assigns that a
So instead of assigning probabilities to strings of a particular length, the aim is to partition the space of possible strings in a way that assigns probabilities to every string, then splits its probability mass between its continuations.
ASHLEY: Hmm. I suppose so.
Okay, I think I buy that the deterministic and probabilistic setups can be made identical for that one specific hypothesis, since it can just assign uniform probabilities to uniform outputs from uniform inputs. And it's trivial for hypotheses that always assign all of their weight to a single sequence. But I can't see how to generalize that to anything more complex. The fair coin hypothesis is the only one where printing the input directly will work.
BLAINE: The key to the generalization is that each probabilistic hypothesis can be specified on a deterministic UTM, and then that hypothesis' measure over binary strings can be mapped on to the measure of possible inputs.
ASHLEY: But it can't randomly sample from possible inputs to produce a distribution of outputs, can it? Or are we positing that this infinitely large computer came with a free True Randomness module to go with its Halting Oracle?
BLAINE: It doesn't need one—just like probabilistic Solomonoff induction takes the total output of all inputs it could receive, so can this one. Why sample when you can just add up the population?
ASHLEY: Okay, explain to me how it would generalize from coins to sensory inputs to give a weight on some deterministic program that somehow outputs my entire life experience followed by the sight of the headline "CANADA INVADES USA". I'll grant you that that's possible under the probabilistic scheme.
BLAINE: Sure. Let's assume we run probabilistic Solomonoff induction on everything you've ever seen and heard and felt, and we land on some set of hypotheses about ways the world could be that predict your life experience relatively well. Some of those will assign some small probability to the sight of "CANADA INVADES USA", as interpreted from your screen by your brain via your eyes.
ASHLEY: Truly tiny, but sure.
BLAINE: If we assume that you're polite enough not to check your phone within the next few milliseconds, there'll be some stream of sensory input bridging from the current moment to whenever you check that headline—let's say tomorrow morning.
ASHLEY: Right, and I suppose some potential sensory streams will give higher conditional likelihoods, like seeing Canadian warplanes overhead or reading that the President denounced this afternoon's bombing of... let's say Detroit.
BLAINE: Sure. Then there's some finite total number of possible sensory streams that you could have, agreed?
ASHLEY: It doesn't feel finite, but I have to concede it can't be infinite.
BLAINE: Every number that isn't infinity is the same to Solomonoff induction. So we can enumerate every sensory stream you could have from now until you open the news tomorrow, and assign a slice of probability to each one—a slice that no other stream can ever get. So we can slowly map the entire space of things-you-can-experience-from-now-until-tomorrow, then add up the total weight of all the ones that end with the sight of "CANADA INVADES USA".
ASHLEY: Sounds like what you described before, sure.
BLAINE: Here's what the deterministic version does: it can have the exact same hypotheses as the probabilistic version. Then, just like the fair coin hypothesis read its input and output a string that was equally complex, the UTM can keep reading more input after the prefix-free code for any particular hypothesis, and interpret it as a decimal. Erm, but a binary decimal... a binaral? I feel like I should have a word for that...
ASHLEY: I know what you mean. I think it's just called a 'binary fraction'.
BLAINE: That'll do. So we can imagine the input continuing to be a more and more precise binary fraction, so that eventually, no matter how it continues, it specifies a specific slice in our enumeration of all your possible experiences. We then say that the UTM outputs that exact experience on seeing that binary fraction.
(whispering) No, that just doesn't sound right...
ASHLEY: Surely not every input can specify some slice—maybe you can make sure that the prefix-free code is complete, but some inputs won't halt, or won't provably halt.
BLAINE: True, but no more so than in the probabilistic domain—same prefix-free code, same computation, so any non-halting program in one domain is present in the other, with exactly the same measure in both.
ASHLEY: Okay, I think I get what you mean by 'measures' before, and I can see how that would lead to the deterministic form mapping all possible inputs on to all possible outputs in a way that exactly matches the probabilistic form. But that's only a limited output, when we want to predict what's coming next, forever and ever, right?
BLAINE: Right. To predict what you see next—that is, exactly how the war plays out for you—we have to enumerate longer sensory streams that divide the probability space more finely. The probabilistic form would have to do the same thing—predict likelihoods of longer streams, and assign them less weight so they can still all add to 1.
ASHLEY: And we can be sure that outputting a particular experience won't be something we regret later, because the input stream now corresponds to some different output? For example, can we be sure that there isn't some stream where following it with "000" predicts that I'll read "CANADA INVADES USA", but "0001" instead predicts "CANADA AND USA NOT AT WAR, EVERYTHING FINE"?
BLAINE: If the probability assignments were consistent in the probabilistic scheme, then yes, we can be absolutely sure. In both cases, it's impossible for the weight on "0001" and "0000" to exceed the weight on "000", so if we split the space of observed data correctly, we can be sure that our outputs match the probabilistic scheme exactly. Adding the "1" on the end might not fully specify what you see after reading "CANADA INVADES USA", but it can't remove that part of the sequence, it can only add to it.
ASHLEY: Hmm... I guess if the deterministic version is just copying the probabilistic version then it's not worse.
It certainly doesn't seem better, though. What's the point if it's just copying the probabilistic scheme?
BLAINE: No, it's not better, nor is it worse—again, it's exactly identical. The probabilistic scheme stops when it gets an input that specifies a program, and then splits the probability space further according to that program. The deterministic scheme starts when it gets an input that specifies a program, uses that program to interpret further input, and splits the probability space further according to that input. One kind has prefix-free encodings of hypotheses, the other has prefix-free encodings of interpreters. For any UTM that does it one way, you can make another UTM that does it the other way.
ASHLEY: You haven't said anything about the other direction—why would a probabilistic version of any deterministic UTM exist?
BLAINE: That's even easier—you just take every program on the deterministic UTM and see what probabilities it assigns to the sequence. Boom, you've converted it back into a probabilistic hypothesis.
ASHLEY: That requires scanning infinitely many... ah, I need to let go of that instinct. You need to scan every possible input, but that's fine, we have a magic computer.
BLAINE: Hypercomputer is the technical term.
ASHLEY: I know, you said.
So on this magic computer, there's an exact equivalence between programs as probabilistic hypotheses, and programs as deterministic interpreters of the rest of the input that started with the interpreter's encoding.
BLAINE: That's right—a precise, 1-to-1 correspondence. A distinction without a difference, as you put it.
ASHLEY: But you said you preferred the probabilistic version. Why?
BLAINE: Several reasons.
Firstly, I find it more intuitive to think about assigning probabilities than measuring spaces of possible inputs. Human beings don't think about the measure of the space of possible conditions that could feed into the Earth's weather system to make it rain tomorrow, we just think about the chance that it'll rain.
Secondly, I think that updating using Bayes' rule is a better model of epistemology than cancelling programs that output incorrect sequences, even though they describe the same shift in the probability space. In the deterministic version, you just keep checking more and more possible inputs to the UTM. The prior likelihood of a program, the posterior likelihood that that program assigns to a particular sequence, and the continuation of that sequence all come from the same source.
But in real life, assigning priors and evaluating posteriors seem to be distinct skills.
In the probabilistic version, they both receive different terms in the equation, even though they're measured in the same unit. There's value in being able to separate parts of an unbounded model that work differently in real life, even when they don't need to be separated if you have a hypercomputer.
ASHLEY: You do, of course, recognize the irony in preferring a version of Solomonoff induction with additional terms that its counterpart lacks?
BLAINE: Hey, I'm a bounded agent that can benefit from additional complexity, so sue me.
There are also distinctions between assigning priors and generating hypotheses, and between evaluating them against what data you have and extrapolating from them to make predictions, neither of which are separated by either version of Solomonoff induction. But the first one is a result of cheating by simply enumerating all hypotheses, and the second is a result of cheating by enumerating all continuations of the sequence, and I'm not aware of any way to get around those.
Anyway, my third reason for preferring the probabilistic version is that determinism requires your hypotheses to predict the data perfectly, which is rarely attainable in real life, while probabilistic hypotheses can be updated and compared against each other even if the ideal hypothesis hasn't been generated yet.
ASHLEY: That all sounds reasonable.
BLAINE: Fantastic! Does that mean all of your questions are answered and you're now convinced that Solomonoff induction is the optimal unbounded solution to epistemology?
ASHLEY: Not at all.
BLAINE: Darn. What's next, then?