In 1999’s The Matrix, life as we know it is actually a virtual reality abstraction; a collection of well-shaped zeroes and ones which add up to an utterly convincing simulation of the real world. Knowing how to manipulate this code — as Morpheus, Trinity, Neo and the rest of the movie’s patent leather-wearing good guys are able — allows them to do anything they want: from throwing crazy kung fu moves to stopping bullets in flight to bending spoons with their mind or leaping tall buildings in a single bound. In short, it lets them repurpose the Matrix’s own computation for almost any application they can dream up.
Several years ago, a then-twenty-something computer scientist named Seth Hendrickson carried out an astonishing (and not entirely dissimilar) demonstration using Nintendo’s classic 1990 side-scrolling platformer, Super Mario World. Like a lot of the geekier members of the Super Mario community, Hendrickson — who is known as “SethBling” on his popular YouTube channel — was fascinated by the possibility of pushing the game far beyond the limits imagined by its creators.
Hendrickson injected Flappy Bird’s 331 bytes of code into Super Mario World‘s unused RAM, and then instructed the processor to execute it.
One of the ways of doing this was to glitch his Super Nintendo console into reading instructions from the system’s RAM instead of the original game cartridge. Since RAM is used to track all parts of the game state, expertly manipulating it makes it possible to set up entirely new game states.
Rather than doing this through traditional, text-based coding, this can achieved by playing the game itself; using gameplay elements such as Mario laying down shells to make the processor read certain instructions from a section of RAM designed to keep track of the placement of these shells. Because these coordinates are stored as a series of bytes, this allows the hacker (Hendrickson in this case) to control what the game’s processor does for a few clock cycles. It lets him seize the game’s code to do whatever he wants.
Confused? Quite possibly — but take Hendrickson’s word that it works. After seeing several limited examples of this “arbitrary code execution” hack in action, Hendrickson had an idea. “The engineer in me knew that if you could trick the processor into running a little bit of code, then you could trick it into running a lot of code,” he told Digital Trends.
Hendrickson teamed up with another member of the community, known as “p4plus2.” Together they showed that it is possible to use this technique to write an entirely new game inside the Super Mario architecture that was designed for, well, Super Mario.
They chose Flappy Bird, the insanely addictive mobile game which enjoyed a brief surge of notoriety in 2014. “[P4plus2] wrote all of the code that ended up going into the Flappy Bird program, and I did most of the work fleshing out the details of the procedure, and practicing to actually be able to execute it,” Hendrickson explained.
“Welcome to the world of the accidentally Turing complete.”
Repeating a series of actions within the game, like a dancer creating a story through movement, he injected Flappy Bird’s 331 bytes of code into Super Mario World‘s unused RAM, and then instructed the processor to execute these bytes as processor instructions. When, after “meticulous planning” and “lots of simulations,” he had finished this, he live-streamed the entire demonstration to 12,000 amazed viewers on Twitch. It remains the largest number of concurrent viewers Hendrickson has ever had.
Achieving Turing completeness
“Welcome to the desert of the real,” says Morpheus in The Matrix after he has stripped away the simulated reality of the virtual world, and shown him the manipulation that lies beneath. In the case of Hendrickson, the phrase might be this: “Welcome to the world of the accidentally Turing complete.”
Achieving Turing completeness sounds like a state of Zen for computer programmers. In fact, it refers to a feature of a computational system — a “universal Turing machine” — that’s able to compute anything, including another computer in some form. Hypothesized in 1936 by Alan Turing, the father of modern computer science, his concept of a Turing machine laid out what we today think of as a general-purpose computer.
A Turing machine must be capable of performing computation by changing states, reading and writing to some form of “tape,” moving said “tape head” left or right, and outputting a final answer in the form of either “accept” or “reject.” Every known algorithm can be converted into a Turing machine and, as a result, can be implemented in any Turing complete system.
“In grade school, I made games in PowerPoint for fun.”
An accidentally Turing complete system is a system which can do all of this without ever meaning to. An accidentally Turing complete system might be designed for, say, guiding a small Italian plumber through game levels to rescue a princess, but it turns out that it can also be made to calculate the digits of pi, solve sudoku puzzles, run Microsoft Windows, or most everything else. It’s the equivalent of an ordinary citizen, living life as an eventful office drone, who suddenly discovers that he or she is more than they think. They’re Neo. They’re the One.
“I like surprisingly [Turing complete] demonstrations because they are often a display of considerable ingenuity,” said Gwern Branwen, who maintains a fairly comprehensive archive of accidentally Turing complete demonstrations online. “It matters,” he continued, “because, if one is clever, it provides an escape hatch from a system which is small, predictable, controllable, and secure — to one which could do anything.”
More where that came from
Given that Branwen hosts an entire archive of accidentally Turing complete systems, it’s no surprise to hear that there are plenty of other examples of the accidentally Turing complete. The game Pokémon Yellow tuns out to be Turing complete. So is Minecraft, the classic Windows time-waster. So is Excel. And far, far more.
“In grade school, I made games in PowerPoint for fun,” said Tom Wildenhain, an undergraduate studying Computer Science at Carnegie Mellon University. “Initially, I stuck to simple things like multiple-choice quizzes and mazes, but I gradually made games with more complicated logic. I actually used PowerPoint for a ton of other non-presentation-related tasks: image editing, 2D animation, and web design. In high school, it was sort of a running joke. My friends would tell me to use ‘real software.’”
In college, Wildenhain took a theoretical Computer Science course where he learned about Turing machines. “I thought, ‘I bet PowerPoint could do that,” he said. It turns out that it could, as he showed in a demonstration carried out for an April 1 joke research conference Carnegie Mellon hosts every year. This mock conference showcases “joke realizations of serious ideas and serious realizations of joke ideas.” “A PowerPoint Turing Machine seemed like a perfect fit,” recalled Wildenhain.
The latest example of an accidentally Turing complete system? Everyone’s favorite geeky card game Magic: The Gathering. “I was on a message board when someone asked whether Magic: The Gathering was Turing complete,” said Alex Churchill, a board game designer and coder. “I thought: What would that even mean?’”
Cue several years of interested research and a recent paper which convincingly demonstrates the idea.
A geeky badge of honor
As the examples above suggest, there is no shortage of accidentally Turing complete pieces of software and games ready and waiting to be discovered. So what exactly should you be looking for when it comes to an accidentally complete Turing system? Like scrabbling through dusty old relics in an attic, there are a few tips that will help treasure-speakers sort genuine artifacts from the trash.
“Many cases of discovering [Turing completeness] seem to consist of simply noticing that a primitive in a system is a little too powerful or flexible,” Branwen said. “For example, if Boolean logic can be implemented, that’s a sign that more may be possible [which can] turn Boolean circuits into full-blown circuit logic for a Turing machine. Substitutions, definitions and abbreviations, regular expressions, or any other kind of ‘search and replace’ functionality is another red flag, as they suggest that a cellular automaton or tag system is lurking. This applies to anything which can change state based on ‘neighbors,’ like a spreadsheet cell or [even] a pixel.”
“Once the genie of [Turing completeness] has been let out of the lamp, it’s difficult to trick it back in, and patch the neck of the bottle.”
According to Alex Churchill, when it comes to tabletop games, candidates include games which allow an unlimited number of turns or actions, are able to store at least one integer number up to a notionally unlimited size (which rules out games where resources are limited), provide scope for actions or events to chain or trigger off one another, and contain a means to control or program which events result in certain other events happening.
Most of the time, discovering accidental Turing completeness is more about a geeky badge of honor than something with immediate application. To return once more to our Matrix analogy, it’s more the equivalent of mental spoon-bending as an after dinner party trick than it is destructive bullet time designed to bring down the existing order. Put simply, with real general-purpose computers in ready supply, there’s no imminent requirement to make our own non-electronic version using decks of Magic: The Gathering cards.
The trouble with Turing?
But there are still risks. Being able to reappropriate ordinary tools for extraordinary purposes comes with potential downside. We don’t tend to think of, say, an MS Word file as a program able to do more than help us write text documents. We have a fixed idea of what software is — and, more importantly, what it does — and this is to our detriment.
Turing completeness shines a light on the fact that computation isn’t something esoteric that only exists in programming languages or computers carefully set up for the task. If a fantasy card game can hold the secrets to computation, then Turing completeness can reside in any reasonably complex system unless it is actively prevented from doing so.
“That we find these demonstrations surprising is itself a demonstration of our lack of imagination and understanding of computers, computer security, and A.I,” Branwen said. “We pretend that we are running programs on these simple abstract machines which do what we intuitively expect. But they run on computers which are bizarre, and our programs themselves turn out to be computers which are even more bizarre.”
He points to the Spectre security vulnerability, which reared its ugly head in 2018 and proceeded to wreak havoc. “Spectre existed for decades in CPU architectures that were extremely closely scrutinized for security problems, but just sort of fell into a collective human blindspot,” Branwen continued. “Nobody thought of controllable speculative execution as being a ‘computer’ which could be ‘programmed’. Once someone noticed — because it was a powerful computer and, of course, Turing complete — it could be used in many ways to attack stuff.”
Branwen suggests that, in the future, there will be more “weird machines” that arise. “Secure systems have to be built by construction,” he said. “Once the genie of [Turing completeness] has been let out of the lamp, it’s difficult to trick it back in, and patch the neck of the bottle.”
For now, though, at least we can all join hands and marvel at how a pair of intrepid computer programmers once coded a version of Flappy Bird inside Super Mario World.
