In The Matrix, Neo sees a black cat walking by. A second later, an eerie feeling creeps over him as the same cat walks by again, making the exact same movements. He finds out that a déjà vu is usually a “glitch in the Matrix,” meaning that their digital reality has been reprogrammed and is now misfiring.
They give a better example of a glitch in the Matrix in Beyond, the first short film in the Animatrix series. Some kids have found a “haunted house” where glass bottles shatter and reassemble, rain falls from a clear sky, broken light bulbs flicker, shadows aren’t attached to the objects that cast them, and they can jump from a height and stop before impact. (A team of “rodent exterminators” clears everyone out and repairs the glitch.)
Neo himself is also a glitch. The Architect tells him: “Your life is the sum of a remainder of an unbalanced equation inherent to the programming of the Matrix. You are the eventuality of an anomaly, which despite my sincerest efforts I have been unable to eliminate from what is otherwise a harmony of mathematical precision.”
When I talk about a glitch in the matrix, I’m not necessarily talking about Neo’s Matrix, but any kind of system that gives a certain perception of reality. The glitch is what shatters that perception, making you realize that the whole thing was an illusion.
During a lucid dream, you’re conscious, but at first you don’t know that you’re dreaming because your brain makes everything so real. However, it doesn’t get everything exactly right. If you just get the idea to test the dream world, you can easily find some glitches: lights that stay on when you flip the switch off, books and clocks that change when you look away, people who say things that don’t make sense, etc. Discovering one glitch tells you it’s all a dream.
Isaac Newton worked out a theory of gravity that held up well to the observations people could make at the time. However, his theory had a rather large glitch that he just swept under the rug. He was forced to assume that a gravitational field propagated at infinite speed. He hated this, but without a theory of relativity, he had no choice.
It was more than 100 years before before observations of Mercury’s orbit showed a glitch, paving the way for a new theory of gravity. Similar things are happening today, as theories of quantum mechanics are being developed to address glitches in classical mechanics at the subatomic level.
Life, the universe, and everything
What is the universe? Essentially, it’s just a very sophisticated program.
This program is made up a number of rules. Things such as “for every action, there is an equal and opposite reaction,” “F = ma,” “E = mc^2,” and so on. But the rules alone don’t do anything. They need some objects to act on. Objects such as you.
Human DNA consists of 3.2 billion pairs of nucleotide bases, with four possibilities for each. This caps the maximum number of genetically distinct people at 4^3,200,000,000 (and in fact far less, since most combinations won’t work).
At conception, your DNA was determined from one of these possibilities. Perhaps you were model #62,085,423,678,990,876,543,357,896,534,567,897,634,524,790,043,446,854,568,987,434,543.
But your DNA didn’t fully describe you, even at such a young age. There were many other factors, such as where and when you were born, what your family was like, etc. But regardless, you were just an object described by a handful of variables.
The objects plus the rules make the system, and now the program is running. But like all programs, it has glitches.
A simple glitch in Doom
I recently stumbled across this page about a bug with the “picked up a medikit” message in Doom. In their rush to revolutionize the first-person shooter genre, id Software apparently didn’t have time to test everything (or retest everything after last-minute changes).
When you pick up a “medikit,” you get an extra 25 health points, and you see a message saying “Picked up a medikit.” If your health was below 25 when you picked it up, the message was supposed to say “Picked up a medikit that you REALLY need!” However, since the code does the < 25 check after adding the 25 health points, the “REALLY need” message will never be displayed:
if (!P_GiveBody (player, 25))
if (player->health < 25)
player->message = GOTMEDINEED;
player->message = GOTMEDIKIT;
The authors of that web page helpfully posted a corrected version of the code. Ironically, the corrected version is much worse than the original:
if (player->health < 25)
player->message = GOTMEDINEED;
player->message = GOTMEDIKIT;
if (!P_GiveBody (player, 25))
If this had been done, the “Picked up a medikit” message would have been displayed even if it wasn’t actually picked up (like if you already had 100% health). The correct fix would have been to simply change 25 to 50 in the original code.
This is just meant to show how easy it is to introduce a glitch. In this case, it’s an easy fix, and it could be made without any complications. But it’s not always that easy.
A more complicated glitch in Pac-Man
Pac-Man theoretically has an infinite number of levels, with no ending. But because of a bug in level 256, it’s impossible to go any further.
The current level is stored as a single byte (8 bits), and therefore can’t get any higher than 255. When it tries to increment to 256, it rolls over to 0. But this actually doesn’t cause any problems, except for one big one with the fruit-drawing routine.
Normally, 0 to 7 fruits are shown at the bottom right, depending on what level you’re on. But when the level counter goes back to 0, the game attempts to draw 256 fruits, corrupting the right half on the screen and leaving an insufficient number of dots to finish the level.
How is this glitch different from the Doom glitch? First, it was much harder to catch. Who would think they needed to test 256 levels of Pac-Man? What player would spend enough quarters to even get close to that point? Why stop at 256? Why not 1,000 or 1,000,000? What about testing what happens when other high numbers get high, like lives, points, or time?
Second, there’s the question of how to fix it. When the level counter goes back to 0, you know it’s really level 256. But there’s no way to know the difference between levels 1 and 257. So how do you know whether to draw 0 fruits or 7? Or should they draw more than 7 fruits at the higher levels? Should they use two bytes to store the level? Then they’d have the same issue at level 65,536. Should they use another bit to indicate the level is 256+, and just leave it at 7 fruits? Should they end the game after level 255? Whatever change they make, they have to retest it.
You can’t fix every bug
But the Pac-Man glitch is still a relatively small issue. Come on, it’s just about drawing a few pieces of fruit. But when programs grow in complexity, they rapidly become more difficult to fix.
In a software engineering class I took, we learned a surprising fact about fixing bugs in a sufficiently complicated program. The number of bugs starts high, and when you start fixing them, the number of course comes down. But the number of bugs can only get so low. Past a certain point, continuing to fix bugs causes the total number of bugs to increase.
I’m not exactly sure what explains this counter-intuitive result. It’s partly because of workarounds that people put in place to accommodate known bugs, which suddenly become bugs themselves when the original bugs are fixed. And it’s partly because people who use the program will come up with new requirements that aren’t properly implemented.
Anyway, since you can’t fix all the bugs, you get to a point where you either have to decide to keep putting out fires, live with the bugs you have, or start over. Starting over isn’t as bad as it sounds: Microsoft wrote Windows NT from scratch to greatly improve a buggy Windows 3.1. And the Architect wanted Neo to start over by rebooting the Matrix and repopulating the Earth from 23 people.
A self-referential trap
In 1998, two companies called Google and Amazon.com were all the rage. Google was a new search engine that we all used because we heard it was the best, but didn’t really know why. And Amazon.com was an online bookstore that claimed to have a book about everything.
When you did a search for something in Google, along with the search results, you’d get a list of books that Amazon.com had on that topic. Search for dogs, and Google said “Amazon.com has these books about dogs…” Search for magnesium phosphate tribasic, and Google said “Amazon.com has these books about magnesium phosphate tribasic…”
It was a little hard to believe. There was no way that Amazon had books about everything. But how could we catch them in a lie?
I figured that a self-referential statement would likely do the trick. I did a Google search for “topics that Amazon.com has no books about.” And Google then said “Amazon.com has these books about topics that Amazon.com has no books about.” Whether such books existed, I didn’t know, but I could be sure that Amazon didn’t have them. This was a glitch in the matrix.
The system needs rules
Google’s problem in that case was that they put no restrictions on what you could type in. But every system needs rules, or it will crash.
A simple example is the liar’s paradox. Consider this sentence: “This sentence is false.” That sentence gives a contradiction, but that’s not really a problem. A consistent system just needs to consist of rules that don’t allow such a sentence to be constructed.
The so-called “naive set theory” in math has a similar flaw, as discovered by British philosopher Bertrand Russell in 1901. Russell’s paradox says this: Let S be the set of all sets that are not elements of themselves. Now, is S an element of S?
If you think about it, you’ll see that the answer is simultaneously yes and no. The paradox can be handled by using a set theory based on axioms that prevent us from forming sets like S. But this safety comes at a price.
Cartoon by xkcd
Gödel’s incompleteness theorems
I’m about to get into a mathematical concept that’s easier to understand in a non-mathematical context. So to warm up, consider this:
- A government big enough to give you everything you want is big enough to take everything you have.
- If our brains were simple enough to understand them, we would be so simple we couldn’t.
- Every justice system either puts some guilty people back on the street, or some innocent people behind bars.
Makes sense, right? The fact that difficulties arise in social systems and our own brain is not surprising. What is surprising is that something similar happens in every mathematical system, where we theoretically have complete control.
In 1931, Austrian logician Kurt Gödel proved his two incompleteness theorems, which I’ve always seen as the best example of a glitch in the matrix. Unfortunately, it gets ridiculously complicated, so I’ll have to do my best to simplify.
In math, we construct things called formal systems. A formal system consists of a language and rules. Examples of formal systems include particular types of arithmetic, geometry, and set theory.
Formal systems can express statements in their language, such as “2 + 2 = 4″ or “Every integer is even.” Some statements are true, and some are false. Also, some statements can be proven, and some cannot.
Ideally, you’d like every statement to be provable if and only if it’s true. That is, you’d like your system to be both consistent (all provable statements are true) and complete (all true statements are provable).
What Gödel proved is that every formal system of sufficient complexity is either inconsistent or incomplete (or both). That is, it’s either too weak to prove everything it should, or it’s strong enough to prove something it shouldn’t. In other words, there’s a glitch in every matrix.
He did this by showing that you can always construct a statement G that essentially says “G is not provable,” but without explicitly referencing itself, and being constructed within the rules of the system. However, self-referential statements aren’t the only ones that can blow up.
Here’s the simplest example I have. Consider the statement “There is no set whose cardinality [size] is between that of the natural numbers and that of the real numbers.” We don’t know whether this statement is true. But we know that in ZFC set theory (the current standard), the statement can’t be proven either true or false.
We’ll eventually figure out whether it’s true or false by jacking out of the matrix and using a more powerful system, but either way, there’s a problem with ZFC set theory. We’ll have a true statement (either the one above, or its negation) that can’t be proven, and therefore ZFC is incomplete (and maybe inconsistent, too).
If there’s a glitch in every matrix, then what is real? How do you define real? Do you think that’s air you’re breathing now?