How Super Mario, Magic: The Gathering, and PowerPoint are low-key supercomputers

Super Mario World

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.”

xiaoice microsoft future of ai assistants alan turing lab right side 1
Alan M Turing (right) is considered the father of modern computing and artificial intelligence. Turing famously helped crack the Enigma code, a complex cypher machine used by the German’s to encrypt messages during World War II.

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.

accidental turing completeness brent krott  15 holds a hand of cards in game called magic the gathering at crossroad games st
Getty Images

“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.

Emerging Tech

Awesome Tech You Can’t Buy Yet: Plant-based shoes and a ukulele learning aid

Check out our roundup of the best new crowdfunding projects and product announcements that hit the web this week. You may not be able to buy this stuff yet, but it sure is fun to gawk!
Product Review

Can Walmart extinguish Amazon’s Fire with the cheap Onn Android tablet?

There aren’t many Android tablets under $100, so the Walmart Onn is an attractive prospect. With near stock Android and the Play Store on board it has the potential to be an Amazon Fire beater, but what’s it like to use?
Product Review

The ZenFone 6 has a flippable camera and is unlike any other flagship phone

Asus is embracing the 2019 trend of not following any trends at all and instead going in its own direction. The ZenFone 6 has a motorized flip-around camera, a 5,000mAh battery, and an almost stock version of Android installed.
Product Review

It's a camera! It's a printer! And it's more fun than it has any right to be

By going digital and adding a built-in mobile printer, the Instax Mini LiPlay puts more features into a smaller form factor than previous Instax cameras, while still being every bit as fun.
Emerging Tech

This drone with hands looks like a nightmare straight out of Black Mirror

This unlikely drone-with-hands creation is the work of Federico Ciccarese, the brains behind YouBionic, a bionic hand project that has evolved far beyond its original brief. Check it out.
Emerging Tech

This crazy-looking robot uses microspines on its legs to climb up walls

Researchers at Carnegie Mellon have built a bioinspired robot, which uses microspines on its feet to grip onto rough surfaces. This allows it to climb up very steep gradients. Check it out.
Emerging Tech

Got $400 million to burn? The world’s largest airplane is up for sale

Stratolaunch, the world's largest airplane, is up for sale. All it'll cost you is $400 million dollars. The brainchild of late Microsoft co-founder Paul Allen, the plane was supposed to make space travel more accessible and affordable.
Digital Trends Live

Digital Trends Live: Florida’s autonomous vehicle law, E3 updates, and more

On this episode of DT Live, we take a look at the biggest trending stories in tech, including Florida allowing fully autonomous vehicles on the road, Atari’s new gaming system, E3 updates, high-speed rail, and more.
Emerging Tech

Ex astris, scientia: Star Trek logo spotted on the surface of Mars

The Mars Reconnaissance Orbiter has been boldly going to Mars and capturing images since 2005, and now it has spotted something where no man has gone before: a structure on the planet's surface which will look familiar to Trekkies.
Emerging Tech

Adobe develops tool to identify Photoshopped images of faces

With deepfake videos making headlines, and campaigns against the Photoshopping of models, people are more aware than ever of the digital manipulation of images. Now Adobe wants to give tools to users to let them spot faked images.
Emerging Tech

NASA’s Mars 2020 rover will pave the way for manned missions to Mars

Survival on Mars is a massive challenge for humanity. To cope with the highly variable temperatures, lack of oxygen and water, and high levels of radiation, the Mars 2020 rover will carry instruments to pave the way for human exploration.
Emerging Tech

Facebook builds virtual homes to train A.I. agents in realistic environments

Researchers at Facebook have created Habitat, which is a platform that enables rapid training for A.I. agents. They will receive thousands of hours of training in just a few minutes in the virtual homes.
Emerging Tech

Impossible Foods struggles to keep up with Impossible Burger demand

Red Robin and White Castle have reported Impossible Burger shortages, as it appears that Impossible Foods is struggling to keep up with demand. The company will be selling its meat-like patties in retail outlets within the year.
Emerging Tech

Pass the salt please: Table salt found on Jupiter’s moon Europa

Astronomers have spotted something unexpectedly familiar on the surface of Jupiter's moon Europa -- sodium chloride, better known as table salt. This suggests the under-ice oceans on Europa are salty and similar to our oceans on Earth.