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