A. The Tape
As the rules of Magic: The Gathering do not contain a ny
concept of geometry or adjacency, encoding the tape itself
is tr ic ky. Our solution is to have many creature tokens with
carefully controlled power and toughness, with each token’s
power and toughness r epresenting the distance fr om the head
of the Tur ing machine. The tape to the left of the Turing
machine’s current read head position is represented by a
series of creature to kens which all have the game colour
green, while th e tape to the right is represented by white
tokens. Our distan c e-counting starts at 2, so there is one 2/2
token representing th e space currently under the head of the
Turing machine; a green 3/3 token represents the tape space
immediately to the left of the Turing head, a gr een 4/4 is
the space to the left of that, and so on. Rogozh in’s universal
Turing mac hine starts with the read head in the middle of the
To represent the symbols on the tape, we use creature types.
We choose 18 creature types from the list of creature types in
Magic to correspond to the 18 symbols in Rogozhin’s (2, 18)
UTM. We can choose th e se creature types to begin with suc-
cessive letters of the alphabet: Aetherborn, Basilisk, Cephalid,
Demon, Elf, Faerie, Giant, Harpy, I llusion, Juggernaut, Kavu,
Leviathan, Myr, Noggle, Orc, Pegasus, Rhino, and Sliver. For
example, a green 5/5 A etherborn token represents that the 1
symbol is w ritten on the 3
cell to the left of the head, and a
white 10/10 Sliver represents that the 18
symbol is written
on the 9
cell to the right of the head. These tokens are all
controlled by Bob, except the most recently c reated token (the
space the Tu ring head has just left) which is controlled by
B. The Controller
Control instructions in a Turing machine are repr esented by
a table of conditio nal statements of the form “if the machine
is in state s, and the last re ad cell is symbol k, then do such-
and-such.” Many Magic cards h ave triggered abilities which
can function like conditional statements. The two we shall use
are Rotlung Reanimator (“Whenever Rotlu ng Reanimator or
another Cleric dies, create a 2/2 black Zombie creature token”)
and Xathrid Necromancer (“Whenever Xathrid Necromancer
or another Human creature you c ontrol dies, create a tapped
2/2 black Zombie creature token”). We will use both, and the
difference between tapped and unta pped c reature tokens will
contribute to the design of the Tu ring m achine.
Each Rotlung Reanimator
needs to trig ger from a dif-
ferent state being read – that is, a different creature type
dying – and needs to encode a different result. Fortunately,
Magic includes cards that can be used to ed it the text of other
cards. The card Artiﬁcial Evolution is uniquely powerful for
our purposes, as it reads “Change the text of target spell or
permane nt by replacing all instanc e s of one creature type with
another. The new creature type can’t be Wall. (This effect
For now we will speak about Rotlung Reanimator for simplicity. Some of
these will in fact be Xathrid Necromancers as explained in the next section.
lasts indeﬁnitely.)” So we crea te a large number of copies
of Rotlung Reanimator and edit e ach one. A similar card
Glamerdye can be used to modify the colour word s with in
Thus, we edit a Rotlung Reanimator by casting two c opies
of Artiﬁcial Evolution replacing ‘Cleric’ with ‘Aethe rborn’
and ‘Zombie’ with ‘Sliver’ and one copy of Glamerdye to
replace ‘blac k’ with ‘white’, so that this Rotlung Reani-
mator now reads “Whenever Rotlung Rean imator or another
Aetherborn dies, create a 2/2 white Sliver creature token ”
This Rotlung Reanimator now encodes the ﬁrst rule of the
program of the (2, 18) UTM: “When reading symbol 1
in state A, write symbol 18 and move lef t.” The Aetherborn
creature token represents symbol 1, the Sliver crea ture token
represents symbol 18, and the fact that the token is white leads
to processing that will cause th e head to move left.
We similarly have seventeen more Rotlung Reanimators
encodin g the rest of the q
program from . Between them
1) Whenever an Aetherborn dies, create a 2 /2 white Sliver.
2) Whenever a Basilisk dies, create a 2/2 green Elf.
Whenever a . . . dies, create a 2/2 . . .
18) Whenever a Sliver dies, create a 2/2 green Cephalid.
See Table II for the full encoding of the program.
C. The Read /Write Head
The operation “read the current cell of the tape” is rep-
resented in-game by forcing Alice to c a st Infest to give all
2. This causes the unique token with 2 tou ghness
to die. It had a colour (green or white) which is irreleva nt,
and a creature type which corresponds to the symbol written
on that cell. That creature type is noticed by a Rotlung
Reanimator, which has a triggered ability that is used to carr y
out the logic encoded in the head of the Turing machine . It
produces a new 2/2 token, co ntaining the information written
to the cell that was just read.
The Turing machine then moves either left or right and
modiﬁes the tokens to keep the tape in order by ad ding
+1/ + 1 counters to all tokens on one side of the head and
1 counters to all tokens on the other sid e. M oving left o r
right will be accomplishe d by casting ﬁrst Cleansing Beam
and then So ul Snuffers.
D. Adding a Second State
Everything described so far outlines the operation of one
state of the Turing machine. However, our Turing machine
requires two states. To ac complish this, we leverage phasing:
an object with phasing can ‘phase in’ or ‘phase out’, and
while it’s phased out, it’s treated as though it doesn’t exist.
We can grant phasing to our Rotlung Reanimators usin g the
enchantment Cloak of Invisibility (“Enchanted creature has
phasing and can’t be blocked except by Walls”) and create a
second set of Ro tlung Reanimat ors to encode th e program
Throughout this paper, card text that has been modiﬁed using cards such
as A rtiﬁcial Evolution is written in italics.