Magic: The Gathering is Turing complete

Discuss

19 Responses to “Magic: The Gathering is Turing complete”

  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?

    • MJSS says:

      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.

      • First Last says:

        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. SamLL says:

    This is quite the Magical Hack.

  3. 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?

    • Buddha Buck says:

      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.

  4. yeastbeast says:

    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.

  5. vonbobo says:

    Land goes on the top row! 

  6. Dave Jenkins says:

    I’m waiting for an actual Glass Bead Game.

  7. bzishi says:

    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.

  8. This is what we used to play for- mathematical achievements- in the days of old Magic. Circa 1994/95.

  9. nemryn says:

    The next step is to ‘program’ it to play Minecraft, then build a redstone computer.

  10. brainflakes says:

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

  11. Ron Gross says:

    No reference at all to the original questions that prompted Alex to create this monstosity :(

    http://draw3cards.com/questions/2851/is-magic-turing-complete 

    Disclaimer: I am the creator of Draw3Cards.

Leave a Reply