An additional problem with Solomonoff induction

Let’s con­tinue from my pre­vi­ous post and look how Solomonoff in­duc­tion fails to ad­e­quately deal with hy­per­com­pu­ta­tion.

You may have heard of the Phys­i­cal Church-Tur­ing the­sis. It’s the idea that the Uni­verse can, in a perfect level of de­tail, be simu­lated on a Tur­ing ma­chine. (No prob­lem if the Uni­verse turns out to be in­finite—the the­sis re­quires only that each finite por­tion of it can be simu­lated.) A corol­lary to the Phys­i­cal CTT is the idea that there are no phys­i­cally re­al­iz­able un­com­putable pro­cesses. We can talk about hy­per­com­put­ers as math­e­mat­i­cal ab­strac­tions, but we’ll never be able to build (or see) one.

We don’t have a very strong sci­en­tific ev­i­dence for the Phys­i­cal CTT the­sis yet—no one has built the perfect simu­la­tor yet, for ex­am­ple. On the other hand, we do have some­thing—all known laws of physics (in­clud­ing quan­tum physics) al­low ar­bi­trary pre­ci­sion simu­la­tions on a com­puter. Even though the com­plete unified the­ory of all fun­da­men­tal forces isn’t there yet, the Stan­dard model already makes pretty ac­cu­rate pre­dic­tions for al­most all en­vi­ron­ments. (Sin­gu­lar­i­ties be­ing the only known ex­cep­tion, as their neigh­bor­hoods are the only lo­ca­tions where the role of quan­tum grav­ity is not neg­ligible.)

So the Phys­i­cal CTT does not con­tra­dict any known laws of physics. Of course, these laws are not con­tra­dicted by a mul­ti­tude of al­ter­na­tive hy­pothe­ses as well; all the hy­pothe­ses which sug­gest that the uni­verse can­not be simu­lated on a Tur­ing ma­chine. We pre­fer the Phys­i­cal CTT solely be­cause it’s the sim­plest one; be­cause Oc­cam’s ra­zor says so.

There are mul­ti­ple lev­els and kinds of un­com­putabil­ity; none of the prob­lems placed on ei­ther of these lev­els are un­com­putable in the ab­solute sense; all of them can com­puted by some hy­po­thet­i­cal de­vices. And all of these de­vices are called hy­per­com­put­ers. A corol­lary to the “Uni­verse is un­com­putable” po­si­tion is that we some­day may be able to, in fact, build a hy­per­com­puter that is em­bed­ded in the phys­i­cal world, or at least ac­cess some of the Na­ture’s mys­ti­cal, un­com­putable pro­cesses as a black box.

Now, the “stan­dard” Solomonoff in­duc­tion uses the Univer­sal prior, which in turn is re­lated to Kol­mogorov com­plex­ity (KC). An un­com­putable pro­cess for­mally has un­defined Kol­mogorov com­plex­ity. In­for­mally, the KC of such as pro­cess is in­finitely large, as it must be larger than the KC of any com­putable pro­cess.

As dis­cussed in the com­ments to the pre­vi­ous post, Solomonoff in­duc­tion is by no means re­stricted to the Univer­sal prior; it can use other pri­ors, in­clud­ing a prior (i.e. prob­a­bil­ity dis­tri­bu­tion) defined over an uni­ver­sal hy­per­com­puter. An ex­am­ple of such a hy­per­com­puter is the com­bi­na­tion Univer­sal Tur­ing ma­chine + Halt­ing prob­lem or­a­cle. Another ex­am­ple is the com­bi­na­tion Univer­sal Tur­ing ma­chine + a true ran­dom num­ber or­a­cle. An up­graded form of Solomonoff in­duc­tion which uses a prior defined over the first kind of uni­ver­sal hy­per­com­puter is go­ing treat the halt­ing prob­lem as a very sim­ple, com­putable pro­cess. An up­graded form of Solomonoff in­duc­tion over the sec­ond kind of uni­ver­sal hy­per­com­puter is go­ing to treat ran­dom num­ber gen­er­a­tion as a very sim­ple, com­putable pro­cess. And so on.

Now here’s the prob­lem. Math­e­mat­i­cally, a Univer­sal Tur­ing ma­chine equipped with the Halt­ing or­a­cle, and a Univer­sal Tur­ing ma­chine equipped with a Ran­dom Num­ber or­a­cle are in the same class: they are both uni­ver­sal hy­per­com­put­ers. Phys­i­cally and prac­ti­cally, they are miles away from each an­other.

A Ran­dom Num­ber or­a­cle is just that: some­thing that gives you ran­dom num­bers. Their statis­ti­cal prop­er­ties won’t even be par­tic­u­larly bet­ter than the prop­er­ties a good pseu­do­ran­dom num­ber gen­er­a­tor. They sim­ply are, in a sense, “true”; there­fore un­com­putable. How­ever, quan­tum physics sug­gests that Ran­dom Num­ber or­a­cles, in fact, might be real; i.e. that there are sources of true ran­dom­ness in the Uni­verse. This is QM in­ter­pre­ta­tion-de­pen­dent, of course, but any de­ter­minis­tic, non-ran­dom in­ter­pre­ta­tion of quan­tum me­chan­ics in­volves things like faster-than light in­ter­ac­tion etc., which frankly are much less in­tu­itive.

A Halt­ing or­a­cle, in con­trast, can solve in­finite num­ber of hugely im­por­tant prob­lems. It’s magic. In my be­liefs, the a pri­ori prob­a­bil­ity that Uni­verse con­tains some sort of Halt­ing or­a­cle is tiny. Only a huge amount of proper sci­en­tific tests could con­vince me to change this con­clu­sion.

On the other hand, math­e­mat­i­cally the two hy­per­com­put­ers are siblings. Both can be ap­prox­i­mated by a Tur­ing ma­chine. Both can even be com­puted by a de­ter­minis­tic al­gorithm (I think?), if the Tur­ing ma­chine that does the com­pu­ta­tion is al­lowed to work for­ever.

There is one sig­nifi­cant math­e­mat­i­cal differ­ence be­tween the two or­a­cles. (Nev­er­the­less, Solomonoff in­duc­tion fails to take into ac­count this differ­ence.) The Halt­ing or­a­cle has a power on its own; it can be used to solve prob­lems even when it comes with­out the ac­com­pa­ny­ing Tur­ing ma­chine. The Ran­dom Num­ber or­a­cle can­not be used for any­thing but ran­dom num­ber gen­er­a­tion. (To solve any com­putable de­ci­sion prob­lem P with the Halt­ing or­a­cle, we can re­for­mu­late it as pro­gram source code: “if P, then halt; oth­er­wise: loop for­ever” and feed this pro­gram to the Halt­ing or­a­cle. In this way the Halt­ing or­a­cle can be used to tell that 3<7 is true—the pro­gram halts -, while 10<5 is false—it loops for­ever.)

The Solomonoff in­duc­tion can be fixed, if we as­sume that the in­put tape of the Univer­sal prior’s Tur­ing ma­chine con­tains in­finite num­ber of ran­dom bits. How­ever, this idea needs an ex­plicit jus­tifi­ca­tion, and its im­pli­ca­tions are not at all ob­vi­ous. Does this mean that Oc­cam’s ra­zor should be “pre­fer the sim­plest hy­poth­e­sis, to­gether with an in­finite source of ran­dom num­bers”, in­stead of “pre­fer the sim­plest hy­poth­e­sis”?

So to sum up, the prob­lem is:

  • In­tu­itively, the prob­a­bil­ity that we are liv­ing in a Uni­verse that in­cludes True Ran­dom num­bers is much larger than the prob­a­bil­ity that we are liv­ing in a Uni­verse that al­lows Halt­ing prob­lem or­a­cles;

  • Solomonoff in­duc­tion can­not re­li­ably dis­t­in­guish be­tween these two cases.

The con­se­quences? When you hear some­one claiming—again—that “com­put­ers are not ca­pa­ble of true cre­ativity/​con­scious­ness/​what­ever, be­cause cre­ativity/​con­scious­ness/​what­ever re­quires hu­man in­tu­ition, which is un­com­putable, etc.”—re­mem­ber that it might be a bad idea to re­spond with an ap­peal to Solomonoff in­duc­tion.

In­ter­est­ingly, quite a few peo­ple praise their in­tu­ition and view it as al­most a mys­ti­cal power, but no one is sur­prised by their abil­ity to name a few ran­dom num­bers :)


A re­lated ques­tion: how does finite, bounded uni­verse fit into this? Does it make sense to use the Univer­sal Tur­ing ma­chine as a gen­er­a­tor for Kol­mogorov com­plex­ity, when the ac­tual model of com­pu­ta­tion re­quired to simu­late the uni­verse is much sim­pler?