Wei Dai writes: > One day, Earth is contacted by a highly advanced alien civilization, and > they tell us that contrary to what most of us think is likely, not all of > the fundamental physical laws of our universe are computable. Furthermore, > they claim to be able to manufacture black boxes that work as oracles for > the Halting Problem of Turing machines (one query per hour). They give > us one free sample, and want to sell us more at a reasonable price. But > of course we won't be allowed to open up the boxes and look inside to > find out how they work.
> So our best scientists test the sample black box in every way that they > can think of, but can't find any evidence that it isn't exactly what > the aliens claim it is. At this point many people are ready to believe > the claim and spend their hard earned money to buy these devices for > their families. So in terms of induction, the situation is that we do test after test to see if this box acts as a halting-problem oracle (HPO, we always need more 3 letter acronyms around here). And it passes all the tests. So then we apply induction and say, since it's acted like an HPO in our tests, we will go ahead and assume that it really is an HPO. The problem is that HPOs are theoretically impossible. We have a proof of it, in fact we have a lot of proofs. So how do we reconcile this? Well, one possibility is that the proof is invalid. It's a pretty simple proof so we look at its assumptions. Fundamentally it assumes that computation is a finitary process. We can only do a finite amount of computation in a finite time. To act as a real HPO it would seem to be necessary for the box in some way to deal with infinities. There would have to be an actual infinity in there somewhere. But again, we generally assume that there are no actual infinities. In physics they are called singularities, which means places where the laws of physics break down. In fact even the prospect of an actual infinity in a theory is seen as a sign that the theory is wrong or incomplete. Relativity puts singularities at the center of black holes, but it is assumed that quantum gravity will fix these, in fact this is one of the main motivations for work on quantum gravity. Disbelief in actual infinities, like disbelief in HPOs, is not really rooted in observation and induction. We don't disbelieve in them simply because our universe seems to be devoid of them. In fact, on the face of things there is evidence that actual infinities may really exist in our universe. Relativity theory has its infinites; there are quantum models which hint at the possibility as well, and even old fashioned Newtonian gravitation on point particles, like is studied in high school physics, implicitly embeds infinities and can construct an HPO. But still, nobody believes that this stuff will work. It's always assumed to be a mistake which future work will correct. (Google hypercomputers or super-Turing computers for some theoretical models of HPOs.) So where does our disbelief come from? Why are we so skeptical? We don't have very good grounds from observation. The mere fact that we've never seen X isn't strong evidence that X doesn't exist. We discover new things all the time, amazing things. Why should HPOs be any different? It seems that our disbelief in HPOs and in other manifestations of infinity is somehow rooted in mathematics itself. We have an instinctive aversion to the possibility of an actual infinity existing as something we can interact with. We believe that mathematics is essentially a finite endeavor, at least in terms of how it manifests in the real world. And yet there are plenty of mathematical models of infinities. The study of transfinites is a very active part of set theory, in fact it is entirely what makes set theory non-trivial. Likewise, with the super-Turing work people have constructed hierarchies of ever more powerful infinity machines. So there is no dearth of mathematical models to deal with infinities. In response to early work on transfinites the mathematical school called constructivism arose. Constructivists reject most of mathematics that deals with infinities. I am not too familiar with the history but I believe that they were concerned about the many potential paradoxes and the possibility that our intuition was a poor guide to truth in the treacherous waters of the transfinites. Constructionism has not gained much ground among mathematicians; I get the impression that it's just not that much fun to do math that way. But it seems to accord well with our instincts about the world. Perhaps we could say that it is all very well for the mathematicians to construct their transfinite castles in the air, but when it comes to reality, we are constructionists. > Fortunately, the Artificial Intelligence in charge of > protecting Earth from interstellar fraud refuses to allow this. Having > been programmed with UD+ASSA (see Hal Finney's 7/10/2005 post for a > good explanation of what this means), it proclaims that there is zero > probability that Halting Problem oracles can exist, so it must be pure > chance that the sample black box has correctly answered all the queries > submitted to it so far. > The moral of this story is that our intuitive notion of induction is not > fully captured by the formalization of UD+ASSA. Contrary to UD+ASSA, we > will not actually refuse to believe in the non-existence of uncomputable > phenomena no matter what evidence we see. Our theories say that it can't happen. Yet in this case we have an observation where it seems like it does happen. So what do we do? It helps in the analysis to distinguish what people actually do from what they "should" ideally do. People are imperfect reasoning machines and there is no fundamental or theoretical interest in explicating every detail of what they believe and what they don't. No doubt it would be possible to build up a complete formal theory and model of a given human brain that would fully explain how it does induction, full of complicated rules and contradictions. That's not the interesting question. The harder question is, what *should* we do, in this situation? I see two possibilities. One is to hold to our theories. No matter how many times we see this machine work, we disbelieve it. We assume it is a trick. Others have suggested ways the trickery might be done. It would be extremely difficult and technologically challenging, but not impossible. These tricks require effort that would be characterized by extremely large numbers, but not infinities. If we are skeptical that they could put such large numbers together, we should be infinitely more skeptical that they can manage infinities. The other possibility is to change our theories, and apply induction. Faced with the evidence of a machine that seems to work, we accept that maybe it really does work. And if so, then our theories are wrong and we need new ones. This is a hard course because of the peculiar grounding of the theories involved. As described above, they aren't based on observation. They are much more fundamental. They have to do with our deepest beliefs about the nature of reality and perhaps even the nature of logic and mathematics. It's questionable to me whether any finite set of observations in the real world has the standing, the philosophical strength, to change our beliefs about the nature of something as ethereal and unphysical as mathematics. But maybe it's the right thing to do. After all, our imperfections, our existence as creatures of a mundane reality, make us prone to error. We might be wrong about anything. Arguably, an optimal induction engine stands ready to change any and every one of its pre-existing beliefs, when they are strongly enough contradicted by the evidence. So perhaps we really should change our minds about mathematics, forget about that constructionism nonsense, and accept that infinities exist and are real, and here's one that we can touch and poke at. > What can we do to repair this flaw? Using a variant of UD, based on a > more powerful type of computer (say an oracle TM instead of a plain TM), > won't help because that just moves the problem up to a higher level of > the computational hierarchy. No matter what type of computer (call it C) > we base UD' on, it will always assign zero probability to the existence of > even more power types of computer (e.g., ones that can solve the halting > problem for C). Intuitively, this doesn't seem like a good feature. > Earlier on this mailing list, I had proposed that we skip pass the > entire computational hierarchy and jump to the top of the set theoretic > hierarchy, by using a measure that is based a set theoretic notion of > complexity instead of a computational one. In this notion, instead of > defining the complexity of an object by the length of its shortest > algorithmic description, we define its complexity by the length of > its shortest description in the language of a formal set theory. The > measure would be constructed in a manner analogous to UD, with each > set theoretic description of an object contributing n^-l to the measure > of the object, where n is the size of the alphabet of the set theory, > and l is the length of the description. Lets call this STUM for set > theoretic universal measure. Are you confident that this is well defined? I understand Schmidhuber's approach: pick an arbitrary UTM, run a random program through it, and take the bit pattern that comes out as the information object. The fraction of programs that produce a given information object is the measure. Is there a similarly mechanical way of understanding the concept of object description in the language of set theory? Can you sketch how that would work? > STUM along with ASSA does a much better job of formalizing induction, but > I recently realized that it still isn't perfect. The problem is that it > still assigns zero probability to some objects that we intuitively think > is very unlikely, but not completely impossible. An example would be a > device that can decide the truth value of any set theoretic statement. A > universe that contains such a device would exist in the set theoretic > hierarchy, but would have no finite description in formal set theory, > and would be assigned a measure of 0 by STUM. > I'm not sure where this line of thought leads. Is induction > unformalizable? Have we just not found the right formalism yet? Or is > our intuition on the subject flawed? The mainstream view, I gather, is that induction is indeed unformalizable. The contrary claim, that induction can be formalized, would be considered controversial. Another way to express the problem is to think of trying to build an optimal induction machine. It could use Bayes theorem to update its beliefs, but what about the priors? Same problem. We could use the Universal Prior but it gives probability 0 to HPOs. Then there are all those other priors that implicitly assume infinite computation, so where does it stop? There are no end to infinities, and as Wei's example shows, there is apparently no place to stand once you start down that road. It would be absurd to suggest, say, that everything up to Aleph-23 has Platonic existence, while infinities from Aleph-24 on up are mere mysticism. Likewise, building a universe out of a UTM+HPO doesn't make sense because as Wei says, there is a 2nd-order HPO, an HPO2, which is beyond the scope of UTM+HPO, so what if the aliens show up with one of those? For a multiverse model to make sense it has to be simple, distinctive and (ideally) unique. We don't quite achieve uniqueness with the UDist (due to the arbitrary choice of a UTM which creates a multiplicative constant difference on measure), which is a major flaw. But adding oracles makes the problem infinitely worse. Here's what I conclude. If we really believe in the Universal Distribution, then we ascribe probability zero to HPOs. That means that in Wei's story, indeed the aliens are tricking Earth. If we try to imagine a universe where the aliens are legitimate and have real HPOs, that is impossible. We are just confusing ourselves if we think such a universe could be real. There is no point in even considering thought experiments based on it, any more than imagining what would happen if aliens showed up with a logical formula which was obviously simultaneously true and false. So given that we stand upon the UDist, there is no need to pay much attention to these kinds of thought experiments. I would suggest that evidence for or against the UDist should come more from the fields of mathematics and logic than from any empirical experience. My hope is that further study will lead to a computational model which is distinguished by its uniqueness and lack of ambiguity. That seems necessary for this kind of explanation of our existence to be successful. Hal Finney