How to turn Magic: The Gathering into a universal Turing machine

Okay, let's just get this out of the way: I used to play Magic: The Gathering. I used to play a lot. It's even possible that I've played fairly recently, although I'm not admitting to anything. But I can feel slightly better about myself, now that it's been shown how you can use Magic cards to create a fully functional Turing machine.

Before we start talking about Magic cards*, let's just make sure we understand what a Turing machine is. Basically, a Turing machine is a kind of computer, and it's called a Turing machine because it was first conceptualized by British mathematician Alan Turing way back in the 1930s before there really were computers.

How A Turing Machine Works

So, the easiest way to describe a Turing machine (in my opinion, anyway) is like this: imagine that you're standing inside a box. Say, a refrigerator box or something. It's open at the bottom, and it's somehow light enough to see things inside the box, because if you couldn't, that would make things needlessly difficult. You are equipped with three objects: a piece of chalk, an eraser and a booklet. The booklet contains a bunch of pages, each with a different set of instructions on it. The cover of the booklet helpfully informs you that you should look down, and then turn to Page 1.

Beneath your feet you see a big number "0" drawn in chalk on the ground. Huh. Turning to Page 1, you read the following instructions:

"If you are standing on a '1,' change it to a '0,' take one step to the left, and turn to Page 3. If you are standing on a '0,' change it to a '1,' take one step to the right, and turn to Page 8."

Having nothing better to do (you're inside a refrigerator box, remember), you erase the "0," draw a "1" where you're standing, and then take a step to the right, refrigerator box and all. There's another "1" on the ground, and you turn to Page 8, which says:

"If you are standing on a '1,' change it to a '0,' take one step to the right, and turn to Page 2. If you are standing on a '0,' do not change it. Take one step to the right, and turn to Page 3."

And that's it. As long as you keep following the instructions and changing the numbers and moving the box, congratulations, you are now a Turing machine.

Traditionally, real Turing machines use a paper tape that moves back and forth and some sort of read/write head with logic programmed into it, but sometimes the actual mechanics of that can be a bit hard to picture. The refrigerator box model is operationally identical. And the reason why Turing machines are so important is that despite their simplicity, a Turing machine can (if you give it a long enough bit of tape and enough time) carry out absolutely any computer algorithm at all. In essence, the CPU inside your computer is just one very big, very fast Turing machine.

Now, the only things that are absolutely required to make Turing machines are the following:

  • A tape with symbols on it (in our refrigerator box example, the tape is the ground, and the symbols are drawn in chalk)
  • Something to read the symbols and write new ones, called a head (you with your eyeballs and the piece of chalk)
  • A table of instructions, or states (the booklet full of pages)
  • A state register (in our example, this would be your brain, which remembers what state you're in and what state to go to next)

Got it? Awesome! So let's take a look at how you can make a Turing machine out of a game of Magic.

Building A Computer With Magic

First, let's go through all the important bits of a Magic Turing machine, starting with the tape.

In order for a Turing machine to work properly, the tape has to be segmented into units (where each unit can hold a symbol), and it also has to be infinitely long. In our refrigerator box example, the unit was the area underneath the box, and stepping to the left or right covered up the old area and exposed a new one. Magic doesn't work that way: there aren't any defined areas to play with. Instead, you have to use creature tokens.

There are two types of tokens in play: Ally tokens, and Zombie tokens. The Ally tokens represent the tape to the right of the head, and the Zombies represent the tape to the left. As you increment units along the tape to the left or right, each creature counter grows by +1/+1, allowing you to have an infinitely long tape. When the tape "moves" one way or the other, an Ally or Zombie token is put into play. All of the other Allies (or Zombies) then either gain +1/+1 or lose -1/-1 to make room for the new token, thereby killing the smallest token of the opposite creature type. This creature death is what triggers the Turing machine to actually perform an operation. Note that the Ally and Zombie creatures are not the symbols on the tape: they're the tape itself.

Next, you need to be able to read symbols and write new ones. This is where the mechanics of Magic come into play: in this case, "reading" a symbol means detecting what color of Ally or Zombie was killed when the tape moved to the right or left. The color is the symbol, and there are three colors in use: red, green and blue. This is where we get into the cards themselves. Reading a symbol is accomplished using a series of heavily (but legally) modified copies of Teysa, Orzhov Scion. Basically, the Tesyas can tell what color of creature died, and then make a new creature of a different color, "reading" the tape and then initializing the first step of the calculation.

tesyas.jpg

The Tesyas also form the table of instructions for the Turing machine. There are always six (!) copies of Tesya in play, although three of them are phased out at any given time. Each triplet of Tesyas has been modified to create a different combination of creature color and type depending on what color of creature dies, and the two separate triplets act as two different sets of instructions in the Turing machine. Going back to our refrigerator box example, the Tesyas would be Page 1 and Page 2 in a two-page booklet of instructions, and changing "pages" is really just the Tesya triplets swapping phases, which is triggered automatically by the game. It's not a lot of variety, but it's all you need for a real Turing machine.

The final piece of the puzzle is the state register. This is simply the "stack," or the cards and actions that are cast and resolved in order according to the rules of the game. To be clear, no input from any of the players (this is a four-player game, incidentally), is required: once the turn begins, the players simply follow all the rules, and the machine executes itself.

And that's it. It's a game of Magic: The Gathering that's a fully operational Turing machine.

The actual operation of the machine is detailed here; it's quite convoluted (and I'm not going to step through it), but obeys all of the rules of the game, albeit a very, very weird pseudo-cooperative version of the game that requires a carefully scripted initial state. Since by definition all operational Turing machines are what's called "Turing complete" — that is, theoretically capable of general purpose computation — it's hypothetically possible to use this game of Magic that we've just described to perform absolutely any calculation that your computer can do. It may be a very difficult program to write, and it may take forever to run, but it's possible to make it happen.

Alex Churchill, via BBG

*I'm unfortunately not going to be able to explain all of the ins and outs of how Magic: The Gathering is played, since this article is absurdly long anyway. If you need help with the basic concepts, ask one of those nerdy kids who you made fun of in high school.

For the latest tech stories, follow DVICE on Twitter
at @dvice or find us on Facebook