An additional problem with Solomonoff induction

Let’s continue from my previous post and look how Solomonoff induction fails to adequately deal with hypercomputation.

You may have heard of the Physical Church-Turing thesis. It’s the idea that the Universe can, in a perfect level of detail, be simulated on a Turing machine. (No problem if the Universe turns out to be infinite—the thesis requires only that each finite portion of it can be simulated.) A corollary to the Physical CTT is the idea that there are no physically realizable uncomputable processes. We can talk about hypercomputers as mathematical abstractions, but we’ll never be able to build (or see) one.

We don’t have a very strong scientific evidence for the Physical CTT thesis yet—no one has built the perfect simulator yet, for example. On the other hand, we do have something—all known laws of physics (including quantum physics) allow arbitrary precision simulations on a computer. Even though the complete unified theory of all fundamental forces isn’t there yet, the Standard model already makes pretty accurate predictions for almost all environments. (Singularities being the only known exception, as their neighborhoods are the only locations where the role of quantum gravity is not negligible.)

So the Physical CTT does not contradict any known laws of physics. Of course, these laws are not contradicted by a multitude of alternative hypotheses as well; all the hypotheses which suggest that the universe cannot be simulated on a Turing machine. We prefer the Physical CTT solely because it’s the simplest one; because Occam’s razor says so.

There are multiple levels and kinds of uncomputability; none of the problems placed on either of these levels are uncomputable in the absolute sense; all of them can computed by some hypothetical devices. And all of these devices are called hypercomputers. A corollary to the “Universe is uncomputable” position is that we someday may be able to, in fact, build a hypercomputer that is embedded in the physical world, or at least access some of the Nature’s mystical, uncomputable processes as a black box.

Now, the “standard” Solomonoff induction uses the Universal prior, which in turn is related to Kolmogorov complexity (KC). An uncomputable process formally has undefined Kolmogorov complexity. Informally, the KC of such as process is infinitely large, as it must be larger than the KC of any computable process.

As discussed in the comments to the previous post, Solomonoff induction is by no means restricted to the Universal prior; it can use other priors, including a prior (i.e. probability distribution) defined over an universal hypercomputer. An example of such a hypercomputer is the combination Universal Turing machine + Halting problem oracle. Another example is the combination Universal Turing machine + a true random number oracle. An upgraded form of Solomonoff induction which uses a prior defined over the first kind of universal hypercomputer is going treat the halting problem as a very simple, computable process. An upgraded form of Solomonoff induction over the second kind of universal hypercomputer is going to treat random number generation as a very simple, computable process. And so on.

Now here’s the problem. Mathematically, a Universal Turing machine equipped with the Halting oracle, and a Universal Turing machine equipped with a Random Number oracle are in the same class: they are both universal hypercomputers. Physically and practically, they are miles away from each another.

A Random Number oracle is just that: something that gives you random numbers. Their statistical properties won’t even be particularly better than the properties a good pseudorandom number generator. They simply are, in a sense, “true”; therefore uncomputable. However, quantum physics suggests that Random Number oracles, in fact, might be real; i.e. that there are sources of true randomness in the Universe. This is QM interpretation-dependent, of course, but any deterministic, non-random interpretation of quantum mechanics involves things like faster-than light interaction etc., which frankly are much less intuitive.

A Halting oracle, in contrast, can solve infinite number of hugely important problems. It’s magic. In my beliefs, the a priori probability that Universe contains some sort of Halting oracle is tiny. Only a huge amount of proper scientific tests could convince me to change this conclusion.

On the other hand, mathematically the two hypercomputers are siblings. Both can be approximated by a Turing machine. Both can even be computed by a deterministic algorithm (I think?), if the Turing machine that does the computation is allowed to work forever.

There is one significant mathematical difference between the two oracles. (Nevertheless, Solomonoff induction fails to take into account this difference.) The Halting oracle has a power on its own; it can be used to solve problems even when it comes without the accompanying Turing machine. The Random Number oracle cannot be used for anything but random number generation. (To solve any computable decision problem P with the Halting oracle, we can reformulate it as program source code: “if P, then halt; otherwise: loop forever” and feed this program to the Halting oracle. In this way the Halting oracle can be used to tell that 3<7 is true—the program halts -, while 10<5 is false—it loops forever.)

The Solomonoff induction can be fixed, if we assume that the input tape of the Universal prior’s Turing machine contains infinite number of random bits. However, this idea needs an explicit justification, and its implications are not at all obvious. Does this mean that Occam’s razor should be “prefer the simplest hypothesis, together with an infinite source of random numbers”, instead of “prefer the simplest hypothesis”?

So to sum up, the problem is:

  • Intuitively, the probability that we are living in a Universe that includes True Random numbers is much larger than the probability that we are living in a Universe that allows Halting problem oracles;

  • Solomonoff induction cannot reliably distinguish between these two cases.

The consequences? When you hear someone claiming—again—that “computers are not capable of true creativity/​consciousness/​whatever, because creativity/​consciousness/​whatever requires human intuition, which is uncomputable, etc.”—remember that it might be a bad idea to respond with an appeal to Solomonoff induction.

Interestingly, quite a few people praise their intuition and view it as almost a mystical power, but no one is surprised by their ability to name a few random numbers :)


A related question: how does finite, bounded universe fit into this? Does it make sense to use the Universal Turing machine as a generator for Kolmogorov complexity, when the actual model of computation required to simulate the universe is much simpler?