Magic: The Gathering is Turing complete

Alex Churchill has posted a way to implement a Turing complete computer within a game of Magic: The Gathering ("Turing complete" is a way of classifying a calculating engine that is capable of general-purpose computation). The profound and interesting thing about the recurrence of Turing completeness in many unexpected places -- such as page-layout descriptive engines -- is that it suggests that there's something foundational about the ability to do general computation. It also suggests that attempts to limit general computation will be complicated by the continued discovery of new potential computing engines. That is, even if you lock down all the PCs so that they only play restricted music formats and not Ogg, if you allow a sufficiently speedy and scriptable Magic: The Gathering program to exist, someone may implement the Ogg player using collectible card games.

A series of Ally tokens controlled by Alex represent the tape to the right of the current head: the creature one step to the right of the head is 1 toughness away from dying, the next one over is 2 toughness from dying, etc. A similar chain of Zombie tokens, also controlled by Alex, represent the tape to the left. The colour of each token represents the contents of that space on the tape.

The operation "move one step to the left" is represented in this machine by creating a new Ally token, growing all Allies by 1, and shrinking all Zombies by one. The details are as follows:

When the machine creates a new 2/2 Ally token under Alex's control, four things trigger: Bob's Noxious Ghoul, Cathy's Aether Flash, Denzil's Carnival of Souls, and Alex's Kazuul Warlord. They go on the stack in that order, because it's Bob's turn; so they resolve in reverse order. The Kazuul Warlord adds +1/+1 counters to all Alex's Allies, leaving them one step further away from dying, including making the new one 3/3. Then Carnival of Souls gives Denzil a white mana thanks to False Dawn (he doesn't lose life because of his Platinum Emperion). Then Aether Flash deals 2 damage to the new token, leaving it 1 toughness from dying as desired. And then the Noxious Ghoul, which has been hacked with Artificial Evolution, gives all non-Allies -1/-1, which kills the smallest Zombie. Depending on whether the smallest Zombie was red, green or blue, a different event will trigger. The machine has moved one step to the left.

If the new token had been a Zombie rather than an Ally, a different Kazuul Warlord and a different Noxious Ghoul would have triggered, as well as the same Aether Flash. So the same would have happened except it would be all the Zombies that got +1/+1 and all the Allies that got -1/-1. This would effectively take us one step to the right.

Magic Turing Machine v4: Teysa / Chancellor of the Spires (via /.)

(Image: Magic the Gathering, a Creative Commons Attribution Share-Alike (2.0) image from 23601773@N02's photostream)


  1. The Stack is a relatively recent addition to MTG mechanics, added because it was a term of craft from computer science that was applicable to the game. This of course implies that MTG is not just Turring Complete, but recursively adaptive as well.

    If we set up a couple of bots playing MTG, will they eventually generate an AI?

    1. The stack was introduced with 6th Edition (1999). Magic-with-the-stack has been around for more than twice as long as Magic-without-the-stack.

      1. To boot, “Magic-without-the-stack” still had a specific resolution order you were supposed to follow for effects. I quit during 4th Edition and (from memory) the only difference in the above procedure would’ve been not having any official priority rules dealing with multiple opponents, but rather only house rules.

  2. As a total noob who learned to play Magic recently so I could play with the kiddos, and as someone who thinks it is an interesting and surprisingly deep game, I just have one question about this post: Huh?

    1. For a system to be “Turing Complete” means it’s possible to implement a Universal Turing Machine (UTM) using it.  A UTM can emulate any Turing Machine (TM), and a Turing Machine can be devised to compute any computable function — in essence, if a computer can compute it, a UTM can do so as well.  In essence, if a system is Turing Complete, it can solve any problem a general purpose computer can (although it’s likely to be slow at it).

      The classic description of a Turing Machine (invented in the 30’s by Alan Turing as a theoretical device) consists of a long paper tape divided into cells along its length, plus a read/write head that can read a symbol (from a finite set of symbols), replace the current symbol with another, and move the tape one cell to the left or the right.  The read/write head is controlled by an internal state and a set of rules of the form “If the current symbol is 1 and the current state is A, then write the symbol 2 to the current cell, go to state C, and shift one cell to the left”.  The tape is theoretically unbounded, which means that when you come to the end of it, you can add more “empty” tape so the machine can keep running.

      To implement a Turing Machine in a system something has to be able to play all the roles of a Turing Machine.  Something has to have the properties of the tape (a sequence of cells which can hold a value, change value at one spot, and be shifted left or right, and is preferably unbounded).  Something has to have the properties of the head (can read the tape, write to the tape, shift the tape, and hold an internal state), and something has to implement the rules table.  If some system is capable of doing all that, it’s Turing Complete.

      It’s surprisingly easy to make a system that’s Turing Complete.  Most people are willing to weaken the “unbounded tape” rule, and just go with “long”.  Physical computers can’t simulate the “unbounded tape” rule, and they do fine.  Once you introduce a way to have arbitrary amounts of state, a way to conditionally loop based on that state, and ways to read and write state, you can usually figure out a way to create a Turing Machine.

      Alex Churchhill, in response to a question on a MTG StackExchange site, devised a set of MTG cards in play, among 4 players, which, when triggered, will emulate a particular  Turing Machine with 2 states and 3 symbols proven in 2007 to be a UTM by Alex Smith.  

      Churchhill’s MTG implementation encodes the parts of a Turing Machine as follows:

      The tape is encoded in two unbounded collections of tokens: a collection of Ally tokens represents the right-hand-side of the tape; and a collection of Zombie tokens represents the left-hand-side of the tape.  The toughness of the token encodes how far the token is from the head: the 1/1 Ally is next to the head, the 2/2 Ally is next to that, etc.  The 1/1 Zombie is next to the head, the 2/2 Zombie is next to that, etc.

      The 3 symbols are encoded in the color of the tokens (red, green, blue).  The Allies and Zombies are of three different colors.

      The 6 rules are encoded by 6 Teysa cards, all of which have been modified by enchantments to read some variation of “Whenever a creature you control goes into a grave yard, put a 1/1 creature token with flying into play”.  The choice of the two colors and the type determine the particular rule.

      The 2 states are encoded by phasing.  Three of the Tesya’s are phased out, and when a state change is desired, the three phased out are phased in and vice versa.

      A cell is read when the Ally or Zombie representing that cell is killed.  That will trigger one of the three phased-in Tesya’s to instigate the rest of the cycle.

      Moving the head to the left is accomplished by adding a new Ally token, which triggers instant powers on a sequence of cards to (a) add a +1/+1 token to each existing Ally and (b) add a -1/-1 token to each existing Zombie.  This will kill the the 1/1 Zombie, triggering a Tesya.

      Moving the head to the right is accomplished by adding a new Zombie token, which triggers instant powers on a sequence of cards to (a) add a +1/+1 token to each existing Zombie and (b) add a -1/-1 token to each existing Ally.  This will kill the 1/1 Ally, triggering a Tesya.

      There are two complications:  The Tesya can only create a creature, it can’t directly trigger a state-change; and it is possible to run out of Allies or Zombies (i.e, run out of tape).

      A Tesya that isn’t changing state will create a colored Ally or Zombie, depending if it wants to go left or right next.  Three of the Tesyas are of that form.  The other three are of the form “…put a +1/+1 white creature…” in play, and other cards are triggered off of the type of creature.  They, in turn, arrange for the casting of a “Time and Tides” card (which switches the phased status of all the Tesyas), kills off the creature created by the Tesya, and then arranges for the creation of the appropriately colored Ally or Zombie. to continue the cycle.

      When the tape runs out, the system halts.  All that has to happen to start it up is have a blue creature die.  In this case, there is a “Rothlings Reanimator” that has been enchanted to put a blue illusion into play whenever a blue illusion dies.  This immediately triggers an card (Aether Flash, used extensively elsewhere in the deck) to kill it (which means it’ll get re-created after everything else is done) and it’s death triggers one of the Tesya’s and we are off and running again.

  3. This requires a lot of cards that are mana-intensive to play (i.e. this is computationally inefficient). The next step is to outsource some Eastern European Magic players to tighten (or should I say Titan?) up the code and make it work on mobile devices.

  4. Here’s to a non-misspent youth! I was just learning important computing algorithms while trying to win that damn Ali from Cairo card and trying to pull off the infinite life/infinite death trick.

  5. > It also suggests that attempts to limit general computation will be complicated by the continued discovery of new potential computing engines. That is, even if you lock down all the PCs so that they only play restricted music formats and not Ogg, if you allow a sufficiently speedy and scriptable Magic: The Gathering program to exist, someone may implement the Ogg player using collectible card games.

    This isn’t really true as such a game would not have arbitrary output (or it presumably wouldn’t be allowed on said app store), so while you could decode an Ogg stream by setting up MTG cards your output would be a re-arranged set of MTG cards.

Comments are closed.