Uh oh. That sounds like the type of thing we famously can’t do. But what are we supposed to do instead, just sit around forever? Could we maybe just junk “0X” after a few million years and call it a day? But what if it turns out that a few million years after that, “0X” settles down and prints out 01101? Then it would be a hit — one of the precious members of set P. And given the failures of “X” and “1X,” it would also be the shortest member, and hence an extremely important contributor to the overall prior on “01101.” So we can’t just junk it without knowing what it ultimately does.
Thus, one of the big issues for the UD: you can’t actually compute it. And not just in a “number of atoms in the universe” sense; rather, in a “whatever is going on with the halting problem” sense. I’m told you can approximate it (see here for a bit more detail), but I don’t have a sense of how this gets around the “what if ‘0X’ is our first big hit?” problem (people sometimes talk about using a “speed prior” instead — e.g., a prior which treats programs as less likely, the longer they take to output a given set of observations — but this, I gather, has its own problems).
I also doubt there’s a way around the “what if ‘0X’ is our first big hit?” problem without making further assumptions (like a speed prior).
Here’s another way to approximate the length of the shortest program that prints out a given string from above: interleave the programs and run them alternatively, increasing the number of different programs being run. Enumerate all of the programs, P1, P2, P3, by length in non-decreasing order.
Then, for each of the steps below, run exactly one step of each program in the step’s list:
1. P1
2. P1, P2
3. P1, P2, P3
4. P1, P2, P3, P4
...
n. P1, P2, …, Pn
...
i.e. at step n, run one more step of programs P1, P2, …, Pn.
Do this while keeping track of the shortest program so far that printed your string (and you can stop running programs that halted or programs that are as long as or longer than your shortest so far). Eventually, you would find the shortest program that prints your string and record it as the shortest so far, and in some cases, you would know that it’s the shortest, if all the shorter programs halt and you wait long enough for them to do so. In many cases, your upper and lower bounds (the length of the shortest program that hasn’t halted yet) will never match, since your lower bound program doesn’t halt.
If you have an infinite enumerable list of hypotheses, you can do the same trick and interleave those as well, and keep track of shortest programs for each hypothesis. With a finite list of hypotheses, you don’t need to interleave, and you can just start them all at the same time.
Of course, this is probably slow, but if you want to make it orders of magnitude faster, I’d expect you to need more assumptions (or maybe use randomness?).
I also doubt there’s a way around the “what if ‘0X’ is our first big hit?” problem without making further assumptions (like a speed prior).
Here’s another way to approximate the length of the shortest program that prints out a given string from above: interleave the programs and run them alternatively, increasing the number of different programs being run. Enumerate all of the programs, P1, P2, P3, by length in non-decreasing order.
Then, for each of the steps below, run exactly one step of each program in the step’s list:
1. P1
2. P1, P2
3. P1, P2, P3
4. P1, P2, P3, P4
...
n. P1, P2, …, Pn
...
i.e. at step n, run one more step of programs P1, P2, …, Pn.
Do this while keeping track of the shortest program so far that printed your string (and you can stop running programs that halted or programs that are as long as or longer than your shortest so far). Eventually, you would find the shortest program that prints your string and record it as the shortest so far, and in some cases, you would know that it’s the shortest, if all the shorter programs halt and you wait long enough for them to do so. In many cases, your upper and lower bounds (the length of the shortest program that hasn’t halted yet) will never match, since your lower bound program doesn’t halt.
If you have an infinite enumerable list of hypotheses, you can do the same trick and interleave those as well, and keep track of shortest programs for each hypothesis. With a finite list of hypotheses, you don’t need to interleave, and you can just start them all at the same time.
Of course, this is probably slow, but if you want to make it orders of magnitude faster, I’d expect you to need more assumptions (or maybe use randomness?).