Magic the Gathering Is Turing Complete
the Gathering is Turing Complete

Magic Turing Machine v5: Rotlung Reanimator / Chancellor of the Spires


How It Works
I'm assuming you're familiar with the basic idea of what a Turing
machine is. There are a few parts to building one in Magic: a tape
extending in two directions storing cells of a few different "colours";
a processing head that can read the current cell's colour, write a new
colour and change its state if necessary; and a "virtual" infinite
tape extending in both directions.
The full list of all cards on the battlefield and in other zones is on the Cards page; this page won't repeat that in full, but will explain why each card is needed.

The Turing Tape
The model of the tape is as follows.
A series of Zombie 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 Yeti tokens, also
controlled by Alex, represent the tape to the left.

Each token has two other creature types, indicating what "colour" the corresponding space on the tape is. For simplicity, in some parts of this discussion I'll refer to these creature types by codes such as A1 rather than by their actual creature types. The types are assigned as follows: (All these types are from the official list of Magic creature types. Where possible I have arranged for the "left" creature type to contain the letter L, the "right" creature type to contain the letter R, and the "common" to contain neither.)

Colour number
Common creature type 
Left creature type
(in addition to Yeti)
Right creature type 
(in addition to Zombie)
Messenger type and direction
1Ape (A0)Ally (A1)Archer (A2)
2Bat (B0)Blinkmoth (B1)Bringer (B2)Basilisk (B1M)
3Cat (C0)Camel (C1)Carrier (C2)
4Demon (D0)Devil (D1)Dragon (D2)
5Eye (E0)Elf (E1)Efreet (E2)
6Fish (F0)Flagbearer (F1)Faerie (F2)Frog (F2M)
7Giant (G0)Golem (G1)Gorgon (G2)
8Hag (H0)Hellion (H1)Harpy (H2)
9Imp (I0)Illusion (I1)Incarnation (I2)Insect (I1M)
10Djinn (J0)Jellyfish (J1)Juggernaut (J2)
11Kavu (K0)Kobold (K1)Kirin (K2)Knight (K2M)
12Leech (L0)Licid (L1)Lizard (L2)Leviathan (L1M)
13Mutant (M0)Moonfolk (M1)Myr (M2)
14Ninja (N0)Noggle (N1)Nightmare (N2)
15Ox (O0)Ooze (O1)Orc (O2)
16Pegasus (P0)Plant (P1)Praetor (P2)
17Rat (R0)Rebel (R1)Rigger (R2)Rhino (R2M)
18Shade (S0)Slith (S1)Siren (S2)Sliver (S1M)

So, for example, any Archer (A2) will also be an Ape (A0) and a Zombie. Being a Zombie indicates it's to the right of the current head position, and being an Ape indicates the space is colour 1 (A). A space of the same colour to the left of the head will be an Ally Ape Yeti.

The operation "move one step to the right" is represented in this machine by creating a new Yeti token (just to the left of where the head was), growing all Yetis by 1, and shrinking all Zombies by 1. The details are as follows:



When the machine creates a new 2/2 Yeti token under Alex's control, three things trigger: Bob's Noxious Ghoul, Cathy's Aether Flash, 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. First, the Kazuul Warlord, which has been hacked with Artificial Evolution, adds +1/+1 counters to all Alex's Yetis, leaving them one step further away from dying, including making the new one 3/3. Second, Aether Flash deals 2 damage to the new token, leaving it 1 toughness from dying as desired. And finally the Noxious Ghoul, which has also been hacked with Artificial Evolution, gives all non-Yetis -1/-1, which kills the smallest Zombie. Depending on the other creature type which this smallest Zombie had, a different event will trigger. The machine has moved one step to the right.
If the new token had been a Zombie rather than an Yeti, 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 Yetis that got -1/-1. This would effectively take us one step to the left.
The tokens' power and toughness need careful adjustment. Rotlung Reanimator naturally makes 2/2 tokens. Each token produced by the read head is affected by two Dralnu's Crusade, giving it +2/+2, and by Curse of Death's Hold and one Engineered Plague, giving it -2/-2. 

The Turing Head
I'm using the simplest two-state Universal Turing Machine, which was published by Yurii Rogozhin in his 1996 paper and has 18 colours of tape. This machine's rules specify what to do in each state when reading a space of each colour. The last few lines of those rules are:

State B, Colour 16: Stay in state B, colour this space 18, move one step right.
State B, Colour 17: Go to state A, colour this space 18, move one step left.
State B, Colour 18: Stay in state B, colour this space 13, move one step left.
State A, Colour 16: Go to state B, colour this space 17, move one step right.
State A, Colour 17: Halt!
State A, Colour 18: Stay in state A, colour this space 3, move one step right.


The key cards to the heart of the Turing machine are Rotlung Reanimator and Artificial Evolution. We use lots of copies of the Reanimator, each one modified to watch for and create a different pair of creature types.

In fact, we use forty-three copies of the Reanimator in the head! They're modified to encode the rules as follows: 
Phased-out Reanimator 16B says "Whenever a Pegasus (P0) dies, make a Siren (S2)."
Phased-out Reanimator 17B says (effectively) "Whenever a Rat (R0) dies, cast Time and Tide, then make a Slith (S1)."
Phased-out Reanimator 18B says "Whenever a Shade (S0) dies, make a Moonfolk (M1)."
Phased-in Reanimator 16A says (effectively) "Whenever a Pegasus (P0) dies, cast Time and Tide, then make a Rigger (R2)."
Phased-in Reanimator 17A says (effectively) "Whenever a Rat (R0) dies, halt the machine."
Phased-in Reanimator 18A says "Whenever a Shade (S0) dies, make a Carrier (C2)."

I hope you can see the correspondence with the programming of the (2, 18) Turing machine. The newly-created token's type indicates what colour the space should be coloured (A-S, skipping Q) and whether to move left or right (1 or 2). Casting Time and Tide corresponds to changing state.


Of course, we can't actually hack a Rotlung Reanimator to say "Whenever a Pegasus dies, cast Time and Tide, then make a Rigger." Casting an instant as a triggered effect is the greatest hurdle this Turing machine needs to get over.

Changing State
In order to repeatedly cast this instant, this version of the Turing machine uses Chancellor of the Spires. This is significantly easier than previous versions which had to use Spellbinder or Toshiro Umezawa.




We use a Necroskitter and Gather Specimens to cause the Chancellor of the Spires to repeatedly enter the battlefield, and Tajuru Archer with a Blight Sickle to kill it. No special tricks need to be done to get the Time and Tide card back where we want it, as the Chancellor lets the instant go back into Cathy's graveyard when it resolves.
So the Reanimators that need to change state actually create tokens that are a different creature type, to avoid triggering the normal Kazuul Warlord / Noxious Ghoul pair, and to trigger the state change instead. I denote these "messenger" creature types with an M suffix.

Reanimator 17B actually says "Whenever a Rat (R0) dies, make a Sliver (S1M)."
Reanimator 16A actually says "Whenever a Pegasus (P0) dies, make a Rhino (R2M)."

These "messenger" token types S1M, R2M etc are not Yetis or Zombies, but they are Reflections. So they don't trigger Kazuul Warlord or Noxious Ghoul, but they do trigger Alex's Tajuru Archer which has been hacked to notice Reflections. They also trigger some further Rotlung Reanimators to make the actual desired tokens when these messenger tokens die. Gather Specimens allows the Rotlung Reanimators to be owned by Bob so their triggers go in the right place on the stack. 



Putting it all together, when we need to change state, this is what happens:

A Rotlung Reanimator makes a messenger token for Alex. Let's say it's of type Sliver (S1M). This is also a Reflection because of a hacked Dralnu's Crusade.
Cathy's Aether Flash triggers, as does Alex's Tajuru Archer. The only creature with flying is Alex's Chancellor of the Spires, so the target is chosen automatically.
Stack: 
...cAF-S1M ; aTA-CotS
Tajuru Archer's ability resolves, and since it has wither because of Blight Sickle, puts enough -1/-1 counters on the Chancellor of the Spires to kill it. Cathy's Necroskitter triggers on the Chancellor's death.
Stack: 
...cAF-S1M ; cNec-CotS
Necroskitter's ability resolves. This tries to return the Chancellor to the battlefield under Cathy's control, but Alex's Gather Specimens means it actually comes back under Alex's control. Cathy's Aether Flash triggers, as does the Chancellor's enter-the-battlefield ability for Alex. The only target for the Chancellor's triggered ability is Time and Tide in Cathy's graveyard.
Stack: 
...cAF-S1M ; cAF-CotS ; aCotS-TaT

Chancellor's ability resolves and Alex casts Time and Tide.
Stack: 
...cAF-S1M ; cAF-CotS ; aTaT

Time and Tide resolves, returning to Cathy's graveyard. All the phasing Reanimators phase in or out.
Stack: 
...cAF-S1M ; cAF-CotS

Aether Flash's ability resolves, dealing 2 irrelevant damage to Chancellor of the Spires, which makes no difference.
Stack: 
...cAF-S1M 

Aether Flash's ability resolves, killing the original Sliver Reflection that triggered this. 
This triggers one of Bob's seven Rotlung Reanimators watching for deaths of messenger tokens. 
Stack: 
...bRR-S1M 

Finally, Bob's Rotlung Reanimator's ability resolves. In this case, this is the Reanimator which noticed the Sliver (S1M) die, and makes a Slith (S1), which is also a Shade (S0) and a Yeti: we've written colour 18 to this space of the tape. Because Alex cast Gather Specimens earlier this turn, the token arrives under Alex's control (so that Kazuul Warlord can see it). This triggers a Kazuul Warlord and a Noxious Ghoul as well as Aether Flash, and the usual processing continues.

Out Of Tape

What do we do if we run out of initialised tape? If the Turing machine moves to a space that hasn't been visited before, the normal processing loop will come to an abrupt halt. The default colour of tape on the Turing machine we're using is 1, so we need a simulation of an infinite tape of empty Ape (A0) spaces � that is, we need to make the machine act as if there were an Ape token that just got killed. 


The solution here is simple. On the bottom of the stack, underneath everything else, there's an ability on the stack from another Rotlung Reanimator under Bob's control, which will make a Construct (under Alex's control due to Gather Specimens). This Construct is an Ape but not a Yeti or Zombie. So it will not trigger any Kazuul Warlords or Noxious Ghouls, and therefore will immediately die to Aether Flash. This triggers Reanimator 1A or 1B just as if there had been an Ape Yeti or Ape Zombie die. And it also triggers Bob's Construct Rotlung Reanimator to put an ability at the bottom of the stack to make another Construct, ready for the next time we exceed the bounds of the tape.

Halting
Finally, what do we do when the machine needs to halt? When we're in state A and see a Rat, that signifies the end of processing, and we need to halt computation.
I decided the machine should cause the game to end, preferably in a way that leaves the tape intact (so that the results can be read from the tape). This at first looked like it'd need to be very complicated, but in fact it's extremely simple. All players are on 1 life, and Alex controls a Vengeful Dead hacked to say "Whenever Vengeful Dead or another Assassin dies, each opponent loses 1 life."

So when a Rat dies while the machine is in state A, this triggers Reanimator 17A, which actually says "Whenever a Rat dies, make an Assassin." The Assassin arrives, only to trigger Aether Flash which promptly kills it. This triggers Vengeful Dead, and when that trigger resolves, everyone except Alex dies and the game ends. The final state of the tape may be read off.

