How would you go about simulating every possible computer program there is?

Based on last post and with some thinking, you might imagine that the answer I’m looking for is something along the lines of “in order of complexity” or “in order of length” or some such. And that’d be… on the right track, yes, but not quite right.

It’s because of that pesky Halting Problem. Some programs never halt, and you can’t even tell in advance, in general. If you just run all programs in order of complexity, eventually you’ll reach some infinite program and never run any of the ones further down the list.

Now, how does Solomonoff Induction work again?

Basically, you… take that list of programs and run them and find the ones that fit the observed data.

You see how that can be problematic. But the answer is fairly simple: dovetailers.

A dovetailer is a machine that takes an ordered list of programs, possibly infinite, with possibly non-halting ones, and then executes them in a breadth-first tree search. What does this mean? Since the list is ordered, what it does is this: it executes the first step of program 1; then the second step of program 1 and the first step of program 2; then the third step of program 1, the second step of program 2, and the first step of program 3; then the fourth step of program 1, the third step of program 2, the second step of program 3, and the first step of program 4; and so on. That way, every program gets executed, no program gets left behind, no one is stuck in non-halting infinite runs, and everyone is happy. Make that list be ordered by length and you’re set.

Suppose you want to dovetail every single program there is, ever. So you make a list and do so. And you know what some of those programs contain? They contain conscious observers. And current cosmological models hold that our universe is infinite, uniform, and ergodic, and it is very likely that every possible arrangement of matter occurs an infinity of times. Which means that you’re in fact a simulation.

And you’re also physical. It’d be more accurate to say that some fraction of your “measure” in the universe (henceforth called magic reality fluid) is simulated, and some fraction is physical. And *you can’t tell which one you are*. Can you? What observation have you ever made that absolutely rules out being simulated somewhere?

That dovetailer that has some “list of all possible programs” however seems quite arbitrary, doesn’t it? Where are you going to store *all possible programs*? How do you even do it? Nah, this is weird. See, there’s another way of building a very simple dovetailer that doesn’t have all possible programs embedded in it, and in fact is a *single* program, but whose emergent behaviour simulates every possible program. Not only that, but it does so in a way that more or less neatly translates directly into Occam’s Razor.

You know what would be a simple way for Occamian behaviour to emerge from a list of programs? What do I even mean by this? Well, suppose that, of all programs from that list that contain *you*, 60% also contain chocolate cake in your kitchen. You’d expect, once you go to your kitchen, to find chocolate cake with 60% probability, right? If you were given that information, there is. So, if in my yet-to-be-revealed formulation of an Universal Dovetailer, something like “simpler programs repeat more often than more complex ones” is true, Occam’s Razor emerges naturally and gracefully from that, right?

Yes, “repeat more often,” because after all, for any function f(x), there is an infinity of programs that compute it. In the list of all possible programs, the program that computes *you* doesn’t happen only once; it happens an infinity of times. For example, take the shortest program that computes you, and then add a single step where it does nothing right before it starts computing you. Both programs compute you, and that step that does nothing… does… nothing! That’s two programs that compute exactly the same thing. So, yeah, many more than just one program contains you. And if, in my idea for a dovetailer it turns out that simpler programs repeat “more often” than complex ones, then Occam’s Razor emerges from that, because then conscious observers found in one of those programs would expect with higher probability that they’re in the simpler program.

A Turing Machine has a finite number of possible actions. If you separate all of its actions as “exclusive,” such that it can only do one of them at a time, then the list of actions are “move head left,” “move head right,” “overwrite symbol under head with 0,” “overwrite symbol under head with 1,” and “halt.” Just those five. Now, imagine a tree. Each node is one of those actions, and each of them has exactly five children, one for each of those actions, too.

L is move left, R is move right, W0 is Write 0, W1 is Write 1, H is Halt. All of these nodes except for H have five more children. This happens forever. And then you just do a breadth-first execution of these programs: in step one, you run each of these 5 programs until their first step, one after the other; then you erase the tape and go to step two, where you run the 20 programs that have two or more steps and the one program that has only one (the program that halts in the first step); you erase the tape again and go to step three, where you run the 75 programs that have three or more steps, the 5 programs that have only two steps, and the program that has only one step; and so on. This way, you will execute every single program there is, simply because those five actions are enough to simulate every single program there is and you’ll repeat every possible combination of them (that halts at H).

Of course, this particular model of a Turing Machine is completely arbitrary. Every other model of computation is exactly similar, however, and you can apply a similar construction to them. That model, as I said, runs every single program that exists; and Occam’s Razor emerges naturally from it: at any given step, the simpler programs are more numerous than the more complex ones. You’re certainly being executed in one of those programs – an infinity of them, actually!

I think. Honestly, at this point, this is all just the equivalent of tumblr nightblogging. I wanted to talk about dovetailers and the possibility of a universal dovetailer, and a dovetailer formulation that didn’t need a list of all possible programs and therefore was actually feasible in the physical universe. Don’t mind me. These are the ramblings of a crazy person.

That first one doesn’t need a list of all programs either, it just needs a subprogram that generates that list. So, I guess it’s just got to simulate a UTM and then go through UTM encodings in order like 0, 1, 00, 01, 10, 11, 100… is that easy?

Not really, because the encoding has to be prefix-free, so there has to be a program that generates all prefix-free encodings in a way that it recognises all of them as programs, and while such a bijection

canof course be created, it depends on details of the UTM.And I mean, I’m not saying that such subprogram can’t be done at all, I’m just saying it’s not particularly easy 😛

Nice blog! One thing I have been wondering about myself is this: could the Halting Problem, and the need for dovetailing to get around it, perhaps be the reason why time exists? If physical reality is the result of computation, but this computation must (because of the Halting Problem) proceed one step at a time through dovetailing, then that could perhaps explain why physical reality unfolds sequentially, why the future is unknown (because the ‘cosmic computer’ can’t predict which computations will halt or not), and why the unfolding of tht future goes step by step…

I don’t think so, because this begs the question by limiting your allowable Turing Machines to TMs that can’t time travel in the first place.

Given that there are an infinite number of possible programmes, how does the dovetailer ever get to the second step of any of them? Doesn’t it just execute first steps forever?

(PS I assume you are familiar with Bruno Marchal and the Everything list.)

Was the explanation on the seventh paragraph not clear enough? I’m unsure how to make it clearer, could you elaborate on your question?