Turing-Complete Video Games
People have been testing the limits of video games, from our favorite classics to newer releases. Speedrunners optimize gameplay, finding the fastest route to beat the game. Glitch finders discover things the game can do that it wasn’t meant to. These players cast aside the intended gameplay experience of being immersed into a story set in a new world, and instead boil down the game to its core essence; a series of inputs and outputs.
Whenever we have a system that can take in an input and give an output, it raises the question of that system’s computational power. Computation in its simplest sense is a process with an input and an output. The platform a video games is run on is constantly performing computations, reading button input and calculating the player’s position, or changing the item selected, or closing a text box. A system with higher computational power can perform more “difficult” computations.
But don’t want to know about the platform’s computational power here. We want to know about the game’s computational power. Within the confines of the game’s mechanics, what kind of computations can we make? In the spirit of testing the limits of video games, what’s the most powerful computation we can do in a given game? Are there games where we can do any computation?
If we have a system that can do every computation, we call it Turing-complete. Many programming languages, understandably, are Turing-complete. If you are reading this electronically, the device you are using is almost certainly Turing-complete. However, many systems exist that are unintentionally Turing-complete. Gwern Branwen gives a non-exhaustive list of such systems, including Microsoft PowerPoint, musical notation, and many video games from Minecraft to Pokémon Yellow. Yes, there exist video games where you could theoretically perform as many computations as a computer can. Here, I will discuss such games and their Turing-completeness.
Note: For us to be able the claim that these video games are Turing-complete, we have to make some assumptions. First, we assume that the game has access to an infinite amount of resources. The technical definition of Turing-completeness requires that the system have an unbounded amount of resources; however, this specification is often ignored in discussions of Turing-completeness, as no physical system could ever meet this requirement. Even the most high-performance supercomputers wouldn’t be considered Turing-complete with this restriction.
Secondly, we will be using generalized versions of these games. We will be ignoring features that would hinder the game’s Turing-completeness, such as limited loading distance and world size or unexpected glitches. It is reasonable to accept these features as non-integral parts of the game; limited world size is most often due to limited resources, as mentioned above, and glitches are unintended features. As we will see later on, though, some games’ Turing-completeness require exploiting glitches.
Examples of Turing-Complete Video Games
Part 1: Games that let you create logical mechanisms
One signifier that a system may be Turing-complete is the presence of logic gates and a way to combine their outputs. Basic gates such as AND and NOR can be combined to create more complicated circuits like adders, which in turn can be combined to create even more complicated circuits.
So, it is no surprise that games with a circuitry-like feature could be Turing-complete. The sandbox-survival game Minecraft’s “redstone” mechanic is a prime example. Redstone is a system similar to real-world circuitry involving various components the player can combine to make all sorts of machines. Creations range from simple automatic farms that detect and harvest fully-grown crops to fully-functional calculators.
The above creation takes input from pressure plates, buttons, and levers. These components have “on” and “off” states, as do most other redstone components. The calculation and display depend on logic gates created with a certain configuration of redstone wire and redstone torches (shown in the image below). The output uses pistons to push blocks out from the base layer and display the answer in readable way; however, this is simply for the user’s benefit. The output could have been shown in binary using redstone lamps, an on-bit shown by a lit lamp and an off-bit shown by a turned-off lamp, without affecting the Turing-completeness.
A similar example is Terraria’s “Hoiktronics”, a combination of the in-game wiring system and a glitch manipulating a character’s speed that allows the creation of machines such as a binary-to-decimal converter.
Part 2: Games that (accidentally) let you create logical mechanisms
It isn’t too surprising a game with circuitry as a feature is capable of powerful computations. But there exist games that are Turing-complete without the presence of a circuitry feature… at least, not one that was designed as a circuitry feature. Like Minecraft, these kinds of games allow for the user to transform input into output using a combination of logic gates, but players have had to be creative with the components they chose to use in their constructions.
A great example is the city-simulation game City: Skylines. Player Daniel Bali discovered a way to construct universal logic gates and make a 4-bit adder in the game. They did so by using three structures in the game: water towers, sewage pipes, and power plants. The properties of these structures are as follows:
- Water towers output clean water if they receive electricity
- Sewage pipes output sewage if they receive electricity
- Power plants output electricity if they receive clean water and sewage
Bali designed an AND gate using electricity into a water tower and a sewage pipe as input and electricity coming out of a power plant as output, since the power plant will produce electricity if and only if the water tower and sewage receive electricity.
Next, they constructed a NOT gate by making use of a mechanic where power plants flooded by sewage cannot produce electricity. A sewage pipe turned on will flood the power plant, preventing electricity from being produced. When the sewage pipe is turned off, the power plant is free to produce electricity.
With a NOT and an AND gate, any other logic gate can be created, meaning much more complex machines could be created, theoretically.
Part 3: Games that (unintentionally) let you write code to the console
Arbitrary code execution (ACE) is a vulnerability in a system where an attacker can run arbitrary code; that is, whatever code they want. Many retro video games are susceptible to arbitrary code execution. However, the methods used to perform ACE on video games differ from those used on, say, PCs. How can a player write code without the ability to write script, or even text in some cases? And how can the player get the system to execute it?
ACE in video games involves two steps:
- Write the code. This is done by manipulating values stored in the game’s RAM. These values can button inputs, sprite positions, score, player-entered names, etc.
- Execute the code. This is done by performing a glitch that moves the program counter. The program counter contains the memory of the current point in the program. The system executes this code and moves to the next line in the program. By moving this counter to the point in RAM containing the values we just manipulated, we can execute it as if it were game code. The glitch needed to execute our code will vary between games.
Since the assembly code the console runs on is Turing-complete, by having a way to write and execute code from within the game, the game itself can be considered Turing-complete.
To explain further, let’s use Pokémon Yellow as an example. Yellow was released in 1998 as an improvement to the original Red and Blue released two years prior. The earliest Pokémon games are notorious for featuring many glitches, ranging from text oversights to save corruption, and a few of these glitches are required for ACE.
By using an item underflow glitch or encountering a certain glitch Pokémon, the player can obtain a glitch item called ws# #m#. Using this item points to the memory in RAM where information about the player’s stored Pokémon is kept, which is information the player can easily change.
The video below shows a tool-assisted speedrun (TAS) of Pokémon Yellow. This TAS involved a computer performing specific inputs on an emulator. As such, the method used here to achieve ACE is different, using save corruption rather than obtaining a glitch item. This method is quicker to perform from a new save file, but incredibly difficult for a human to perform correctly.
Players have also discovered how to use ACE in Super Mario World. YouTuber SethBling was able to inject the instructions for Flappy Bird into the classic SNES game by manipulating the coordinates of the sprites on screen.
Conclusion
Hearing that a video game is as powerful as a computer sounds incredible at first, but there is little realistic purpose of a game being Turing-complete. Computers are complicated machines, but this is not because of their computational ability. Turing-completeness is actually not that hard to achieve. As discussed in parts 1 and 2, all we need to solve a computational problem is input that runs through a series of logic gates which compute an output, and these features aren’t particularly rare.
The true power of a computer, rather, comes in its performance. Computers make efficient use of time and space, which is where other Turing-complete systems fall flat. The 4-bit adder shown in City: Skylines took 20 real-life minutes to compute a single addition. A fully-functional redstone computer in Minecraft would likely take more storage than the computer that runs the game would need.
Additionally, all the assumptions and generalizations made at the beginning are further limiting factors. In Minecraft, redstone only works up to a certain distance from the player, meaning larger systems simply wouldn’t work. The creator of the City: Skylines adder mentioned having trouble in debugging their creation as randomly occurring lightning would disconnect the power lines needed for the circuit.
One could also challenge the validity of the claims of certain games being Turing-complete. The City: Skylines example only demonstrated a simple 4-bit adder, and while this is compelling evidence of Turing-completeness, it is by far a definitive proof of computational power. Examples utilizing arbitrary-code execution can also seem wishy-washy, since the computational power can only be obtained with unintended mechanics. Put differently, the “ideal” Pokémon Yellow would not have such exploits.
Questioning the computational abilities of video games ultimately has no real-world applications. Yet, it is a way for us to conceptualize about the utmost power of a system, to not worry about practicality but instead focus on what is theoretically possible. In other words, it’s just another way to test the limits of the games we know and love.