The incomplete algorithm

A paper this week in the Journal of Holography Applications in Physics left me scratching my head.

To get why it's so puzzling -- and why not only I (an admitted layperson), but some actual physicists, are inclined to doubt its rather earth-shattering conclusion -- a little background first.

A few months ago I wrote here at Skeptophilia about Kurt Gödel's Incompleteness Theorem.  This astonishing piece of work, published in 1931, dashed the hopes of people like David Hilbert that it could be proved that a purely algorithmic system like mathematics was both complete (all true statements that can be expressed within it are provable) and consistent (all provable statements that can be expressed within it are true).  Gödel proved, beyond any doubt, that mathematics cannot be both; if it is consistent, it is incomplete (some true statements are unprovable); if it is complete, it is inconsistent (some provable statements are untrue).

It was a devastating result.  We think of math as being cut-and-dried, a system where there's no fuzzy ambiguity.  Turns out there's a built-in flaw (although some might object to my calling it that); and not just mathematics, but any sufficiently powerful algorithmic system you could invent, would fall to the same death blow.

The other piece of background is also something I've dealt with here before; the possibility that we might live in a simulation.  The claim has been seriously considered by people like Nick Bostrom (of the University of Oxford) and David Kipping (of Columbia University); they looked at the questions of (1) if we were in a simulation, how we could tell, and (2) if simulation is possible, what our chances are of inhabiting the real, original universe (turns out, a fairly persuasive argument concludes that it's near zero).  Of course, that doesn't settle the truth of the major premises; (1) are we in a simulation? and (2) are simulations possible?, respectively.  And as anyone who's taken a course in logic knows, if the first part of a syllogism is false, you can conclude any damnfool thing you want from it.  (More accurately, if the major premise is false, the conclusion could be true or false, and there's no way to tell for sure.)

Okay.  So what this week's paper did is to look at the possibility of our being in a simulation, from a Gödelian perspective.  And their conclusion was that if the universe is a simulation, then it is by definition an algorithmic system, because anything that is runnable on a computer (even a super-powerful one) would have to be, at its basis, a set of algorithms.  Therefore, by Gödel's Theorem, there would have to be true statements that are unreachable from within the system, meaning there is more to the universe than can be reached from inside the simulation.  Conclusion: we can't be in a simulation, because it would be inherently incomplete.

My first thought on reading this was that I must be misinterpreting them, because the conclusion seemed like an enormous overreach.  But here is a quote from one of the authors, Mir Faizal of the University of British Columbia - Okanagan:

Drawing on mathematical theorems related to incompleteness and indefinability, we demonstrate that a fully consistent and complete description of reality cannot be achieved through computation alone.  It requires non-algorithmic understanding, which by definition is beyond algorithmic computation and therefore cannot be simulated.  Hence, this universe cannot be a simulation.

And another, by study co-author Lawrence Krauss, of Australian National University:

The fundamental laws of physics cannot be contained within space and time, because they generate them.  It has long been hoped, however, that a truly fundamental theory of everything could eventually describe all physical phenomena through computations grounded in these laws.  Yet we have demonstrated that this is not possible.  A complete and consistent description of reality requires something deeper -- a form of understanding known as non-algorithmic understanding.

So I don't think I'm misunderstanding their logic -- although I will certainly defer to wiser heads if there are any physicists in the studio audience.

The problem for me is that it is yet to be shown that the universe is non-algorithmic.  I'll buy that if it is algorithmic, there will be truths we can't reach by mathematical logic; so if this were a simulation, there'd be parts of it we couldn't get at.  But... so what?  I have no problem imagining a sufficiently complex simulation that gave such a convincing appearance of reality that any unreachable truths would be remote enough we might not have found them.

I think Faizal et al. may have too high an opinion of the capacity of the human brain for elucidating the workings of the universe.

Turns out I'm not the only one who has issues with this paper.  Physicist Sabine Hossenfelder did a brilliant take-down of the Faizal et al. study, and in fact gave it a nine out of ten on her infamous Bullshit Meter.  She said:

Unfortunately, [the paper] assumes its major premise.  We have never measured any quantity that is provably uncomputable.  To assume we can do this is logically equivalent to assuming we don't live in a simulation.  To see what I mean, let me turn their argument around.  Maybe the fact that we have never measured any quantity we can't also compute is proof that we are part of an algorithm that simulates the universe...  

We don't know any counterexamples.  The cases which I've mentioned that have been discussed in the literature always take some limit to infinity.  For example, they might use infinitely many atoms.  Or a lattice with an infinitely small spacing...  In these mathematical idealizations, yes, there are quantities that provably can't be computed in a finite time.  But we don't know any real-world examples.  Not a single one.  Isn't that weird?  It's like we actually can't measure anything that an algorithm could not also compute.  So maybe... we are algorithms.

In conclusion, the headlines I've seen, along the lines of, "Physicists Prove We're Not In A Simulation," strike me as a bit premature.  We haven't escaped from Bostrom and Kipping's matryoshka universe quite that easily.  Me, I'm going to stay in the "I don't know" column.  The Simulation Hypothesis certainly hasn't been proven, but despite Faizal et al., I don't think it's going to be easy to disprove, either.

So I guess we haven't settled whether the insane *gestures around vaguely at everything* we've been dealing with is real, or is (as I've suggested before) the result of stoned aliens twiddling the knobs just to fuck with us.  I'm honestly not sure which would be worse, frankly.

****************************************

Escaping the bottle

Two years ago, I wrote a post about the work of Nick Bostrom (of Oxford University) and David Kipping (of Columbia University) regarding the unsettling possibility that we -- and by "we," I mean the entire observable universe -- might be a giant computer simulation.

There are a lot of other scientists who take this possibility seriously.  In fact, back in 2016 there was a fascinating panel discussion (well worth watching in its entirety), moderated by astrophysicist Neil deGrasse Tyson, considering the question.  Interestingly, Tyson -- who I consider to be a skeptic's skeptic -- was himself very accepting of the claim, and said at the end that if hard evidence is ever found that we are living in a simulation, he'll "be the only one in the room who's not surprised."

Other participants brought up some mind-boggling points.  The brilliant Swedish-American cosmologist Max Tegmark, of MIT, asked the question of why the fundamental rules of physics are mathematical.  He went on to point out that if you were a character inside a computer game (even a simple one), and you started to analyze the behavior of things in the game from within the game -- i.e., to do science -- you'd see the same thing.  Okay, in our universe the math is more complicated than the rules governing a computer game, but when you get down to the most basic levels, it still is just math.  "Everything is mathematical," he said.  "And if everything is mathematical, then it's programmable."

One of the most interesting approaches came from Zohreh Davoudi, also of MIT.  Davoudi is studying high-energy cosmic rays -- orders of magnitude more energetic than anything we can create in the lab -- as a way of probing the universe for what amount to glitches in the simulation.  It's analogous to the screen-door effect , a well-known phenomenon in visual displays, where (because there isn't sufficient resolution or computing power to give an infinitely smooth picture) if you zoom in too much, images pixellate.  The same thing, Davoudi says, could happen at extremely high energies; since you'd need an infinite amount of information to simulate behavior of particles on those scales, glitchiness in extreme conditions could be a hint we're inside a simulation.  "We're looking for evidence of cutting corners to make the simulation run with less demand on memory," she said.  "It's one way to test the claim empirically."

The reason this comes up is because of a recent paper by Roman Yampolskiy (of the University of Louisville) called, simply, "How to Hack the Simulation?"  Yampolskiy springboards from the arguments of Bostrom, Kipping, and others -- if you accept that it's possible, or even likely, that we're in a simulation, is there a way to hack our way out of it?

The open question, of course, is whether we should.  As I recall from The Matrix, the world inside the Matrix was a hell of a lot more pleasant than the apocalyptic hellscape outside it.

Be that as it may, Yampolskiy presents a detailed argument about whether it's even possible to hack ourselves out of a simulation (and answers the question "yes").  Not only does he, like Tegmark, use examples from computer games, but also describes an astonishing experiment I'd never heard of where the connectome (map of neural connections in the brain) of a roundworm, Caenorhabditis elegans, was uploaded into a robot body which then was able to navigate its environment exactly as the real, living worm did.  (The more I think about this experiment, the more freaked out I become.  Did the robotic worm know it was in a simulated body?)

Evaluating the strength of Yampolskiy's technical arguments is a bit beyond me, but to me where it becomes really interesting is when he gets into concrete suggestions of how we could get a glimpse of the world outside the simulation.  One method, he says, is get enormous numbers of people to do something identical and (presumably) easy to simulate, and then simultaneously all doing something different.  He writes:

If, say, 100 million of us do nothing (maybe by closing our eyes and meditating and thinking nothing), then the forecasting load-balancing algorithms will pack more and more of us in the same machine.  The next step is, then, for all of us to get very active very quickly (doing something that requires intense processing and I/O) all at the same time.  This has a chance to overload some machines, making them run short of resources, being unable to meet the computation/communication needed for the simulation.  Upon being overloaded, some basic checks will start to be dropped, and the system will be open for exploitation in this period...  The system may not be able to perform all those checks in an overloaded state...  We can... try to break causality.  Maybe by catching a ball before someone throws it to you.  Or we can try to attack this by playing with the timing, trying to make things asynchronous.

Of course, the problem here is that it's damn near impossible to get a hundred people to cooperate and follow directions, much less a hundred million.

Another suggestion is to increase the demand on the system by creating our own simulation -- a possibility Bostrom and Kipping considered, that we could be in a near-infinite nesting of universes within universes.  Yampolskiy says the problem is computing power; even if we're positing a simulator way smarter than we are, there's a limit, and we might be able to exploit that:

The most obvious strategy would be to try to cause the equivalent of a stack overflow—asking for more space in the active memory of a program than is available—by creating an infinitely, or at least excessively, recursive process.  And the way to do that would be to build our own simulated realities, designed so that within those virtual worlds are entities creating their version of a simulated reality, which is in turn doing the same, and so on all the way down the rabbit hole.  If all of this worked, the universe as we know it might crash, revealing itself as a mirage just as we winked out of existence.

In which case the triumph of being right would be cancelled out rather spectacularly by the fact that we'd immediately afterward cease to exist.

The whole question is as fascinating as it is unsettling, and Yampolskiy's analysis is at least is a start (along with more technical approaches like Davoudi's cosmic ray experiments) toward putting this on firmer scientific ground.  Until we can do that, I tend to agree with theoretical physicist James Sylvester Gates, of the University of Maryland, who criticizes the simulator argument as not being science at all.  "The simulator hypothesis is equivalent to God," Gates said.  "At its heart, it is a theological argument -- that there's a programmer who lives outside our universe and is controlling things here from out there.  The fact is, if the simulator's universe is inaccessible to us, it puts the claim outside the realm of science entirely."

So despite Bostrom and Kipping's mathematical argument and Tyson's statement that he won't be surprised to find evidence, I'm still dubious -- not because I don't think it's possible we're in a simulation, but because I don't believe that it's going to turn out to be testable.  I doubt very much that Mario knows he's a two-dimensional image on a computer monitor, for example; even though he actually is, I don't see how he could figure that out from inside the program.  (That particular problem was dealt with in brilliant fashion in the Star Trek: The Next Generation episode "Ship in a Bottle" -- where in the end even the brilliant Professor Moriarty never did figure out that he was still trapped on the Holodeck.)

So those are our unsettling thoughts for the day.  Me, I have to wonder why, if we are in a simulation, the Great Simulators chose to make this place so freakin' weird.  Maybe it's just for the entertainment value.  As Max Tegmark put it, "If you're unsure at the end of the day if you live in a simulation, go out there and live really interesting lives and do unexpected things so the simulators don't get bored and shut you down." 

Which seems like good advice whether we're in a simulation or not.

****************************************