Polarized gamma rays and manifest infinity

Yes, these are certainly good arguments, and valid as far as they go. But I'm not sure they entirely solve the problem.

For concreteness, suppose what the aliens sold us is not a black box, but a sheet of paper with a thousand digit binary number written on it, claimed to be the first thousand bits of Chaitin's omega (which they claim to have generated using a halting oracle that works by a hack they discovered that allows them to exploit the infinite computation underlying physics). We quickly verified the first few bits, then over the next couple of generations verified a few more bits at decreasing rate.

Omega is algorithmically random, so as far as Solomonoff induction is concerned, no matter how many bits are verified, the probability of the next bit being correct is 50%. On the other hand, we humans assign a higher probability than that, based on a nonzero credence that the whole sequence is correct; and this credence becomes higher the more bits are verified.

It is true that computable humans cannot consistently beat SI in the long run. But does that not just mean in this case that we cannot verify indefinitely many bits of omega? For all the other bits written on that page, there is a fact of the matter regarding whether they are right or wrong. Supposing they are indeed right, do we not still end up holding a more accurate belief than SI, even if we have difficulty translating that into winning bets?

Even assuming that efficiency-as-elegance is epistemically relevant, efficiency can only be defined relative to a model of computation, and there is no reason to think that the model of computation we usually have in mind, due to being familiar with such computers in our daily lives, is relevant for what is efficient/elegant for the universe.

Would you also say that our observations don't necessarily follow a simplicity prior because there's no reason to think our notion of simplicity (which is also defined only relative to a model of computation) is relevant for the universe?

Indeed, once I realized quantum mechanics took exponential computing power, I considered this inelegant until I concluded the many-worlds interpretation means it's being put to good use after all. Is that a case of ending up at the right belief for the wrong reason? On the one hand you could say SI doesn't bat an eyelid at exponentially inefficient computation. On the other hand you could say it does, when you take into account the need to specify spacetime coordinates of the observer as well as underlying laws; in a sense, that discourages too much inefficiency of the wrong sort.

Having said that, I'm inclined to think continuum arithmetic isn't the 'wrong sort' of inefficiency in this sense. But see my reply to Daniel - how do you bite this bullet without making the 'arbitrary choice of basis' limitation much worse?

I suppose we'll find out when we reach a high enough tech level to be able to build our own halting oracles, and promptly get sued. If the lawsuit rests on a claim that we reverse engineered the one we bought, it must be copyright law; if the lawsuit doesn't even need to claim that, it must be patent law.

I see no reason to think that galactic law will resemble ours. Extremely vague concepts like "intellectual property" are about as close of an analogy as we're likely to get.

Si.

What you say is true as far as that goes; if it were only a case of getting precision in observed physical quantities proportional to the precision of our measurements, I wouldn't be so bothered about it.

But things like the Born probabilities on electron spin measurements, or the gamma ray observations, suggest that a small number of bits being given to us as measurements are backed by much higher precision calculations behind the scenes, with no obvious way to put an upper bound on that precision.

In particular, we had for a long time been thinking of the Planck scale as the likely upper bound, but that now appears to be broken, and I'm not aware of any other natural/likely bound short of infinity.

An alternative interpretation of the halting oracle hypothesis that does involve a manifest infinity: There is a program of infinite length (and infinite information content) that solves the halting problem. It contains all the digits of Chaitin's constant.

Interesting! Looking quickly over the argument, what it seems to be saying is this (someone please correct me if I'm misunderstanding it):

• We already know that anyone with a solution to an NP problem can convince us of this in P time. (This is obvious for some NP problems e.g. propositional satisfiability, but surprising for others e.g. traveling salesman.)

• Surprisingly, a variant of this extends to all PSPACE problems, if the verification procedure is allowed to be an interactive dialogue and if we are satisfied with an exponentially small probability of error. This applies even to problems like chess, via the application of nontrivial (but still polynomial time) transformations.

But it's not jumping out at me how to extend something like this to incomputable problems. Do you have an approach in mind?

Aliens who have solved chess can convince us of that fact without showing us the solution. It would be somewhat surprising if aliens who have a halting oracle could not.

Damn, the argument is in a postscript file. That would require downloading something. I wonder if I care that much!

I don't think the situation is comparable.

Recall that in the chess case the setup is this: the verifier is given a string of n random bits, asks P(n) interactive questions to the alien, and then says yes or no. If White can force a win in chess the verifier says yes in 2/3s of the cases, while if White cannot force a win the verifier says yes in only 1/3d of the cases.

It's a deep result that you can set up a verification protocol like this for any problem in PSPACE. But it's easy to see that it only works if the problem is in PSPACE: using P(n) space, the alien can simulate all possible question-answer interactions with the verifier, and give the answers that will make the verifier answer yes if there are any at all. So you could never use a protocol like this to prove that you possess a halting oracle, since even without an oracle you can do a finite amount of computation to figure out what answers the verifier will accept.

I would guess this principle holds in general: no matter which particular notion of "proof" or "convincing" you settle on, it will ultimately involve running a finite computation to verify a purported proof. But such a procedure can always be fooled by another (longer) finite computation.

(Edit: corrected error in the description of the protocol)

I find this suspect. If someone who was only good enough at chess to make moves at random played against a chess master, the latter would win so often that if they play for any reasonable amount of time, the former could never tell if the latter is capable of losing.

I don't think so. Think of it this way, even when we consider only computable universes, we distinguish between the size of the description and the size of the output. If we counted across outputs, we would expect the observed universe to be a random bit stream, therefore we would expect to be Boltzmann brains, therefore we would expect to observe only the minimum order necessary for observation at all. As we actually observe much more order than this, we believe the right way to do it is to count across descriptions with a prior biased towards shorter ones. And even uncountably infinite universes can have finite descriptions.

Or maybe it's being run on a one-dimensional cellular automaton or a Turing machine etc. What of it? Regardless, the system in question is simulating space with, apparently, a granularity of at least 1e-48 meters, and there remains the question of whether it is using finite or infinite computing power.

That may indeed end up being the best solution to the problem. On the other hand, what formal language do we write such definitions in? SI already has the limitation that you have to supply a basis of computation, the choice of which weakly affects the result (additive constant on Kolmogorov complexity (in practice small), multiplicative constant on measure). Is there a way to use definitions which are not necessarily algorithms, so as to get a formally precise result without making this limitation much worse?

Well we can observe what answer it gives for the next case we run it on, and the next, and the next. So there is still the question of whether we expect, given that the box has passed every case we were able to test, that it will continue to give the right answer for future cases.