# Magic: The Gathering is Turing Complete

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/magic-the-gathering-is-turing-complete

- **Authors:** Alex Churchill et al.
- **Published:** 2019
- **Topic:** Computer Science
- **Original:** https://s3-us-west-1.amazonaws.com/fermatslibrary/uploads%2F1635729405520-g4hb37o0qdg-55f3f2761920e48124381bd36e7ccbdb%2Fmagic.pdf
- **Pages:** 8
- **Annotations:** 20 comments in 20 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/magic-the-gathering-is-turing-complete

## Annotations

### Annotation 1 (page 1)

Beside the passage: “Magic: The Gathering is Turing Complete”

**Annotation** by João Batalha (2021-11-02):

> ### Magic The Gathering
> Magic: The Gathering is a trading card game created by the American mathematician and inventor Richard Garfield (great-grandson of U.S. President James A. Garfield) and released in 1993. Garfield was influenced by his passion for the roleplaying game Dungeons & Dragons.
>
> Magic is considered to be the first trading card game. It successfully combined elements of board games and card collecting. During a game of Magic, two players compete by leveraging their homebuilt deck of cards to defeat their opponent by spending "mana" to play creatures, spells and other items. Players can customize their deck before each battle, choosing cards from their own library. More than 20,000 different cards have been released for Magic: The Gathering since its release and there are an estimated 20 million players all over the world.
> ![](https://i.imgur.com/j2HEE0p.jpg)
> *Two players playing Magic: the Gathering*

### Annotation 2 (page 1)

Beside the passage: “The core of this paper is the c onstruction presente d in Section IV: a universal Turing machin e embedded into a game of Magic: The Gathering. As we can arrange for the victor of the game to be determined by the halting behaviour of the Turing machine, this construction establishes th e following theorem:”

**Annotation** by João Batalha (2021-11-02):

> ## Playing Magic
> The full rules of Magic are extensive - you can find the official document [here (https://media.wizards.com/2021/downloads/MagicCompRules%20202109224.pdf), which is over 250 pages long.
>
> #### Overview of game
> A typical game of Magic usually involves two players. Each player has their own deck of cards, either one previously constructed or made from a limited pool of cards for the event. A player starts the game with a "life total" of twenty and loses the game when their life total is reduced to zero. A player's life total is typically reduced via an attack by an unblocked creature or by direct damage caused by spells. A player can also lose if they must draw from an empty deck. Some cards specify other ways to win or lose the game. Additionally, the "Golden Rule of Magic" states that "whenever a card's text directly contradicts the rules, the card takes precedence".
>
> If you wish to learn how to play Magic, [this video](https://www.youtube.com/watch?v=RZyXU1L3JXk) is a good resource.

### Annotation 3 (page 1)

Beside the passage: “Prior to this work, no u ndecidable real games were known to exist. Demaine an d Hearn (2009) [10] note that almost every real-world game is trivially decidable, as they produce game trees with only computable paths. They further note that Rengo Kriegspiel 1 is “a game humans play that is not obvio usly decidable; we …”

**Annotation** by João Batalha (2021-11-02):

> Rengo Kriegspiel is a "blindfolded", team variant of Go. There are two teams with two players each, a referee and five Go sets. The players move alternatingly. Each player keeps track of their own moves on their own board; they are not informed about teammates' or opponents' moves. The referee keeps track of the complete game and informs a player if their move was illegal, in which case they can try again. The referee removes captured stones from all affected boards.
> ![](https://i.imgur.com/UlI4r8W.png)
> *A game of Rengo Kriegspiel*

### Annotation 4 (page 1)

Beside the passage: “Magic: The Gathering (also known as Magic) is a popular trading card game owned by Wizards of the Coast. Formally, it is a two-player zero-sum stochastic card game with imperfect informa tion, putting it in the same category as games like poker and hearts. Unlike those games, players desig n their own custom decks ou …”

**Annotation** by João Batalha (2021-11-01):

> Zero-sum games are 2-player games where the sum of the payoffs of the players is 0 - these are games of pure competition between the players. Zero-sum stochastic games are dynamic zero-sum games played in discrete time with probabilistic transitions between states. In games with imperfect information (like Poker) there might be certain parts of hidden state that are not visible to one or more players

### Annotation 5 (page 1)

Beside the passage: “The approach of embedding a Turing machine inside a game directly is generally not considered to be feasible for real-world games [10]. Althoug h some open-world sandbox games such as Minecraft and Dwarf Fortress can support the construc tion of Turing machines, those machines have no strategic relevance and those …”

**Annotation** by João Batalha (2021-11-02):

> Example of a Turing Machine built by a player in Minecraft
> ![](https://i.imgur.com/Ri3E1aW.png)

### Annotation 6 (page 1)

Beside the passage: “In this paper, we examine Magic: The Gathering from the point of view of algorithmic game theory, looking at the computational complexity of evaluating who will win a game. As most games have ﬁnite limits o n their complexity (such as the size of a game board) most research in algorithm ic game theory of real-world …”

**Annotation** by João Batalha (2021-11-01):

> As the authors state, there are a number of real world games that show non-trivial computational complexity:
>
> - **Tetris** - If the sequence of pieces is given, it is NP-complete to determine whether it is possible to keep the stack below a finite height
> - **Crossword puzzle construction** - NP-complete
> - **Dots-and-boxes** - NP-hard
> - **Mahjong Solitaire** - NP-complete
> - **Minesweeper** - coNP-Hard
> - **FreeCell** - NP-Complete
> - **Jigsaw puzzles** - Jigsaw puzzles can be formalized in a variety of ways, different edge matching rules, different boundary conditions, etc. Many versions are NP-Complete
> - **Lemmings** - NP-Complete

### Annotation 7 (page 1)

Beside the passage: “Even when looking at generalised games, very few examples of undecid a ble games are known. On an abstract level, the Team Computation Game [ 9] shows that some games can be undecid able, if they are a particular kind of team game with imperfect information. The authors also present an equivalent construction in their …”

**Annotation** by João Batalha (2021-11-02):

> Caulombe and Lynch were able to reason about those video games by structuring them into an abstract game on graphs that serves as a simplification of the Team Computation Game they mention (which is undecidable).
>
> Here is an example of how they built those graphs leveraging elements of a game (Super Smash Bros in this case):
> ![](https://i.imgur.com/dCuwf4F.png)
>
> If you are curious to learn more about it, here is the [paper](https://drops.dagstuhl.de/opus/volltexte/2018/8805/pdf/LIPIcs-FUN-2018-14.pdf) by Caulombe and Lynch.

### Annotation 8 (page 2)

Beside the passage: “investigating algorithmic and artiﬁcial intelligence approaches to playin g Magic, including Ward and Cowling (2009) [15], Cowling et al. (2012) [6], and Esche (2018) [11]. Esche (2018) brieﬂy considers the theoretical computational complexity of Magic and states an op en problem that has a positive answer only if …”

**Annotation** by João Batalha (2021-11-02):

> Unlike games like Chess and Go, researchers still haven't been able to develop an AI capable playing magic at the level of the best human Magic players.

### Annotation 9 (page 2)

Beside the passage: “This paper complete s the project started by Churchill [4] and continued by Churchill et a l. [5] of embed ding a u niversal Turing machine in Magic: The Gathering such that determining the outcome of the game is eq uivalent to determining the halting of the Tur ing machine. This is the ﬁrst result showing that there …”

**Annotation** by João Batalha (2021-11-02):

> Rice's Theorem states that all nontrivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior for a given set of inputs (e.g. does the program terminate for all inputs), unlike a syntactic property (e.g.  does the program contain a go-to statement)

### Annotation 10 (page 2)

Beside the passage: “In [4], the author presents a Magic: The Gathering endgame that embeds a universal Turing machine. However, this work ha s a major issue: it’s not qu ite deterministic. At several points in the simulatio n, players have the ability to stop the computation at any time by opting to decline to use effects that say “may.” …”

**Annotation** by João Batalha (2021-11-02):

> ![](https://i.imgur.com/UmfRdn6.jpg)

### Annotation 11 (page 2)

Beside the passage: “In this work, we solve this problem by reformulating the construction to exclusively use cards with mandatory effects. We also substan tially simplify the most co mplicated aspect of the construction, the recording of th e tape, and reduce the construction from one involving four players to one involving two, and whic …”

**Annotation** by João Batalha (2021-11-02):

> ### Rogozhin Turing Machines
> When Alan Turing came up with the idea of a universal machine he had in mind the simplest computing model powerful enough to calculate all possible functions that can be calculated.
>
> Turing Machines are generally defined with a set of symbols (which can be written to the "tape") and a set of states that the Turing Machine can be in. The natural question is: What is the smallest possible Turing Machine?  Claude Shannon showed that two symbols were sufficient so long as enough states were used (or vice versa), and that it was always possible to exchange states for symbols.
>
> Yurii Rogozhin worked on finding the smallest universal Turing Machines. Generally, the syntax for Universal Turing Machines is $UTM(m; n)$ - which denotes the class of universal Turing machines with $m$ states and $n$ symbols.

### Annotation 12 (page 2)

Beside the passage: “II. PRELIMINARIES One initial challenge with Magic: The Gathering is the encodin g of infor mation. Som e cards ask players to choose a number. Although rules for how to specify a number are not discussed in the Compreh e nsive Rules [16], convention is that players are allowed to specify n umbers in any way that both …”

**Annotation** by João Batalha (2021-11-02):

> Cards mentioned by the authors:
> ![](https://i.imgur.com/KktkX2L.jpg)
> ![](https://i.imgur.com/Muk7kBO.jpg)
> ![](https://i.imgur.com/ns2jzg2.jpg)
> ![](https://i.imgur.com/R0hYhxL.jpg)

### Annotation 13 (page 3)

Beside the passage: “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 …”

**Annotation** by João Batalha (2021-11-02):

> #### What is a Creature Token?
> Creature tokens are effectively markers that represent a creature card with specific properties. Creature tokens can be created as the result of a spell for instance. Creature Tokens are not actual Magic cards. They cannot exist in your hand or deck. While playing the game, players can use whatever is more player friendly for them to represent a creature token with specific properties (e.g. die, piece of torn paper, etc).

### Annotation 14 (page 3)

Beside the passage: “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 Reanimator now reads “Whenever Rotlung Rean imator or another Aetherborn dies, create a 2/2 …”

**Annotation** by João Batalha (2021-11-02):

> ![](https://i.imgur.com/TkQmL50.jpg)

### Annotation 15 (page 3)

Beside the passage: “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 successive letters of the alphabet: Aetherborn, Basilisk, Cephalid, Demon, Elf, …”

**Annotation** by João Batalha (2021-11-02):

> Rogozhin's (2,18) Turing Machine is a Turing machine with 2 states and 18 different symbols (that can be written to the "tape")

### Annotation 16 (page 3)

Beside the passage: “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 suchand-such.” Many Magic cards h ave triggered abilities which can function like conditional statements. The two we shall use are …”

**Annotation** by João Batalha (2021-11-02):

> ![](https://i.imgur.com/KXbMR8g.jpg)
> ![](https://i.imgur.com/QmIDXIC.jpg)
> ![](https://i.imgur.com/4tOqPt4.jpg)

### Annotation 17 (page 3)

Beside the passage: “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/ − 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 …”

**Annotation** by João Batalha (2021-11-02):

> ![](https://i.imgur.com/j7hi0HL.png)
> ![](https://i.imgur.com/bKSaDmW.jpg)
> ![](https://i.imgur.com/nlR78ll.jpg)
> ![](https://i.imgur.com/S3zGlk7.jpg)

### Annotation 18 (page 4)

Beside the passage: “if able.” When the card resolves, it would normally be put into her graveyard, but Alice is enchanted by Wheel of Sun and Moon, which causes it to be placed at the bottom of her library instead, allowing her to redraw it in the future and keeping the cards she needs to cast in order. After her upkeep step, Alice …”

**Annotation** by João Batalha (2021-11-02):

> ![](https://i.imgur.com/JzoBkQm.jpg)
> ![](https://i.imgur.com/KOgOpih.jpg)
> ![](https://i.imgur.com/mfrzt5F.jpg)
> ![](https://i.imgur.com/JzQtbet.jpg)
> ![](https://i.imgur.com/Ode71ig.jpg)

### Annotation 19 (page 4)

Beside the passage: “T3 If the Turing machine is remaining in the same state,”

**Annotation** by João Batalha (2021-11-02):

> ![](https://i.imgur.com/cz2y2uY.jpg)
> ![](https://i.imgur.com/NmRaCyd.jpg)

### Annotation 20 (page 7)

Beside the passage: “We choose to encode halting as making Alice win th e game. When the Turing machine doesn’t change state, Alice casts the card Coalition Victory on her third turn. It reads “You win the game if you control a lan d of eac h basic land type and a creature of e ach color.” This normally accomplishes nothing because she …”

**Annotation** by João Batalha (2021-11-02):

> ![](https://i.imgur.com/x7qX86o.jpg)
> ![](https://i.imgur.com/dITxN0c.jpg)

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

arXiv:1904.09828v2 [cs.AI] 23 Apr 2019

Magic: The Gathering is Turing Complete [Annotation 1]

Alex Churchill Indepe ndent Researcher Cambridge, United Kingdom alex.churchill@cantab.net

Stella Biderman Georgia Institute of Technolo gy Atlanta, United States of America stellabiderman@gatech.edu

Austin Herrick University of Pennsylvania Philadelphia, United States of America aherrick@wharton.upenn.edu

Abstract—Magic: The Gathering is a popular and famously complicated trading card game about magical combat. In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem, solvin g a problem that has been open for a decade [1], [10]. To d o this, we present a methodology for embeddin g an arbitrary Turing machine into a game of Magic such that the ﬁrst player is guaranteed to win the game if and only if the Turing machine halts. Our result applies to how real Magic is played, can be achieved using stand ardsize tournament-legal decks, and does not rely on stochasticity or hi dden information. Our result is also highly unusual in that all moves of both players are forced in the construction . This shows that even recognising who wi ll win a game in which n ei ther player has a non-trivial decision to make for the rest of the game is undecidable. We conclude with a discussion of the implications for a un iﬁed computational theory of games and remarks about the playability of such a board in a tournament setting.

I. INTRODUCTION

Magic: The Gathering (also known as Magic) is a popular trading card game owned by Wizards of the Coast. Formally, it is a two-player zero-sum stochastic card game with imperfect informa tion, putting it in the same category as games like poker and hearts. Unlike those games, players desig n their [Annotation 4] own custom decks ou t of a card-pool of over 20,000 cards. Magic’s multifaceted strategy has made it a p opular topic in artiﬁcial intelligence researc h.

In this paper, we examine Magic: The Gathering from the point of view of algorithmic game theory, looking at the computational complexity of evaluating who will win a game. As most games have ﬁnite limits o n their complexity (such as the size of a game board) most research in algorithm ic game theory of real-world games has primarily looked at generalisations of commo nly played games rather than the real-world versions of the games. A few real-world games have been found to have non-trivial complexity, inc luding Dots-and- [Annotation 6] Boxes, Jenga and Tetris [8]. We believe that no real-world game is known to be h arder than NP previous to this work.

Even when looking at generalised games, very few examples of undecid a ble games are known. On an abstract level, the Team Computation Game [ 9] shows that some games can be undecid able, if they are a particular kind of team game with imperfect information. The authors also present an equivalent construction in their Constraint Logic fra mewo rk that was used by Coulombe and Lynch (2018) [7] to show th a t some video [Annotation 7] games, including Super Smash Bros Melee and Mario Kart, have u ndecidable gen eralisations. Constraint Logic is a highly

successful and highly ﬂexible framework for modelling games as computations.

The core of this paper is the c onstruction presente d in Section IV: a universal Turing machin e embedded into a game of Magic: The Gathering. As we can arrange for the victor of the game to be determined by the halting behaviour of [Annotation 2] the Turing machine, this construction establishes th e following theorem:

Theorem 1: Determining the outcome of a game of Magic: The Gathering in which all remain ing moves are forced is undecid able.

A. Previous Work

Prior to this work, no u ndecidable real games were known to exist. Demaine an d Hearn (2009) [10] note that almost every real-world game is trivially decidable, as they produce game trees with only computable paths. They further note that Rengo Kriegspiel [Annotation 3] 1 is “a game humans play that is not obvio usly decidable; we are not aware of any other such game.” It is conjectured by Auger and Teytaud (2012) [1] that Rengo Kriegspiel is in fact undecidable, and it is posed as an open problem to demonstrate a ny real game that is undecida ble.

The approach of embedding a Turing machine inside a game directly is generally not considered to be feasible for [Annotation 5] real-world games [10]. Althoug h some open-world sandbox games such as Minecraft and Dwarf Fortress can support the construc tion of Turing machines, those machines have no strategic relevance and those games are deliberately design e d to su pport large-scale simulation. In contrast, leading formal theory of strategic game s claims tha t the unbounded memory required to simulate a Turing machine entirely in a game would be a violation of the very natur e of a game [9].

The computational complexity of Magic: Th e Gathe rin g in has been studied previously by several authors. Our work is inspired by [4], in which it was show n that four-player Magic can simulate a Turing machine under certain assumptions about player behaviour. In that work, Churchill conjectures that these limitations can be removed and preliminary work along those lines is discussed in [5]. The com putational complexity of checkin g the legality of a particular decision in Magic (blocking) is investigated in [3] and is found to be coNP-complete. There have also been a number of papers

1 Rengo Kriegspiel is a combination of two variations on Go: Rengo, in which two players play on a team alternating turns, and Shadow Go, in which players are only able to see their own moves.

#### Page 2

investigating algorithmic and artiﬁcial intelligence approaches to playin g Magic, including Ward and Cowling (2009) [15], Cowling et al. (2012) [6], and Esche (2018) [11]. Esche (2018) [Annotation 8] brieﬂy considers the theoretical computational complexity of Magic and states an op en problem that has a positive answer only if Magic e nd-games are decidable.

B. Our Contribution

This paper complete s the project started by Churchill [4] and continued by Churchill et a l. [5] of embed ding a u niversal Turing machine in Magic: The Gathering such that determining the outcome of the game is eq uivalent to determining the halting of the Tur ing machine. This is the ﬁrst result showing that there exists a real-world game for which deter mining the winning strategy is non-computable, answering an open question of Demaine and Hearn [10] and Auger and Teytaud [1] in the positive. This result, combined with Rice’s Theorem [13], also answers an open problem from Esche [11] in the [Annotation 9] negative by showing that the equivalen c e of two strategies for playing Magic is undecidable.

This result raises important f oundational questions about the nature of a game itself. As we have alr eady discussed, the leading formal theory of games holds that this construc tion is unreasonable, if not impossible, and so a reconsideration of those assumptions is called for. In section V-A we discuss additional foundational assumptions of Constraint Logic that Magic: The Gathering violates, and present our interpreta tion of the implications for a uniﬁed theory of ga mes.

C. Overview

The paper is structured as follows. In Section I I we provide backgr ound information on this work , including previous work on Magic Turing machines. In Section III we present a sketch of the construction and its key pieces. In Section IV we provide the full construction of a universal Tu ring machine embedded in a two-player game of Magic. In Section V we discu ss the game-theoretic and real-world implications of our result.

II. PRELIMINARIES One initial challenge with Magic: The Gathering is the encodin g of infor mation. Som e cards ask players to choose a number. Although rules for how to specify a number are not discussed in the Compreh e nsive Rules [16], convention is that players are allowed to specify n umbers in any way that both players can agree to. For example, you are allowed to choose the number 2 100 or ⌈log 177⌉. This presents an issue brough t to our attention by Fortanely [12]. Consid e r the following situation: both playe rs control Lich, Transcendence, an d [Annotation 12] Laboratory Maniac. O ne player then casts Menacing Ogre. The net effect of this play is the “Who Can Name the Bigger Number” game – whoever picks the biggest number wins on the spot. This makes identifying the next board state noncomputable [2], so we require that any numbers speciﬁed by a playe r mu st be expressed in stand ard binary notation.

We believe that with this r e stric tion Magic: The Gathering is transition-computable, meaning that the function that maps a

board state and a move to the next board state is computable 2 . However, it is unclear how to prove this beyond exhaustive analysis of th e over 20,000 card s in the game. We leave that question open for future work:

Conjecture 1: The function that takes a board state and a legal move and returns the next b oard state in Magic: The Gathering is c omputable. In this conjecture we say “a legal move” because it is also not obvious that checking to see if a move is legal is computable. Chatterjee and Ibsen-Jensen [3] show that checking the legality of a particular kind of game action is coNP-complete, but the question ha s not be e n othe rwise considered. Ag ain, we leave this for future work:

Conjecture 2: There does not exist an algorithm for checking the legality of a move in Magic: The Gathering .

A. Previous Magic Turing Machines

In [4], the author presents a Magic: The Gathering endgame that embeds a universal Turing machine. However, this work ha s a major issue: it’s not qu ite deterministic. At several points in the simulatio n, players have the ability to stop the computation at any time by opting to decline to use effects that say “may.” For example, Kazuul Warlord read s “Whenever [Annotation 10] Kazuul Warlord or another Ally enters the battleﬁeld under your control, you may p ut a +1/ + 1 counter on each Ally you con trol.” Declining to u se this ability will interfe re with the Turing machine, either causing it to stop or cau sin g it to perform a different calculation from the one intende d. The construction as given in Churchill [4] works under the assumption that all players that are given the option to do something actually do it, but as the a uthor notes it fails w ithout this assumption. Attempts to correc t this issue are discussed in Churchill et al. [5].

In this work, we solve this problem by reformulating the construction to exclusively use cards with mandatory effects. We also substan tially simplify the most co mplicated aspect of the construction, the recording of th e tape, and reduce the construction from one involving four players to one involving two, and whic h only places constraints on one player’s d eck, matching the format in which Magic is most commonly played in the real world (two-player duels). Like the previous work, [Annotation 11] we will embed Rog ozhin’s (2, 18) universal Turing machine [14].

III. AN OVERVIEW OF THE CONSTRUCTION In this section we give a big picture view of the Turing machine, with full d etails deferred to the next section. The two players in the game are named Alice and Bob.

To construct a Turing machine in Magic: The Gathering requires thr ee main elements: the tape which encodes the computation, the c ontroller which determines what action to take next ba sed on the current state and the last read cell, and the read/write head which interacts with the tape under the control of the controller.

2 We avoid the term “computable game” which is more commonly used to mean that the game has a computable winning strategy.

2

#### Page 3

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 [Annotation 13] 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 tape [14].

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) [Annotation 15] UTM. We can choose th e se creature types to begin with successive 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 st symbol is w ritten on the 3 rd cell to the left of the head, and a white 10/10 Sliver represents that the 18 th symbol is written on the 9 th 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 Alice.

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 suchand-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”) [Annotation 16] 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 3 needs to trig ger from a different 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

3 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 card text.

Thus, we edit a Rotlung Reanimator by casting two c opies of Artiﬁcial Evolution replacing ‘Cleric’ with ‘Aethe rborn’ [Annotation 14] and ‘Zombie’ with ‘Sliver’ and one copy of Glamerdye to replace ‘blac k’ with ‘white’, so that this Rotlung Reanimator now reads “Whenever Rotlung Rean imator or another Aetherborn dies, create a 2/2 white Sliver creature token ” 4 . This Rotlung Reanimator now encodes the ﬁrst rule of the q 1 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 1 program from [14]. Between them they say:

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 represented in-game by forcing Alice to c a st Infest to give all creatures − 2/ − 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/ − 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. [Annotation 17]

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

4 Throughout this paper, card text that has been modiﬁed using cards such as A rtiﬁcial Evolution is written in italics.

3

#### Page 4

TABLE I GAME STATE WHEN THE (2, 18) UTM BEGINS

Card Controller Changed text / choices / attachment 29 Rotlung Reanimator Bob See Table II 7 Xathrid Necromancer Bob See Table II 29 Cloak of Invisibility Alice attached to each Rotlung Reanimator 7 Cloak of Invisibility Alice attached to each Xathrid Necromancer Wheel of Sun and Moon Alice attached to Alice Illusory Gains Alice attached to latest tape token Steely Resolve Alice Assembly-Worker 2 Dread of Night Alice Black Fungus Sliver Alice Incarnation Rotlung Reanimator Alice Lhurgoyf, black, Cephalid Rotlung Reanimator Bob Lhurgoyf, green, Lhurgoyf Shared Triumph Alice Lhurgoyf Rotlung Reanimator Alice Rat, black, Cephalid Rotlung Reanimator Bob Rat, white, Rat Shared Triumph Alice Rat

Card Controller Wild Evocation Bob Recycle Bob Privileged Position Bob Vigor Alice Vigor Bob Mesmeric Orb Alice Ancient Tomb Alice Prismatic Omen Alice Choke Alice Blazing Archon Alice Blazing Archon Bob

q 2 . At the moment we read the current cell, exactly one set of Rotlung Reanimato rs will be phased in.

Objects with phasing phase in or out at the beginning of their c ontroller’s turn, effectively toggling between two states. Accordingly we will arr a nge for the turn cycle to last 4 turns for each player when no state chan ge occurs, but just 3 turns when we need to chan ge state.

IV. THE FULL CONSTRUCTION Now we will provide the full construction of the Magic: The Gathering Turing machine and walk thr ough a computational step. The outline of one step of the comp utation is as follows (Bob’s tur ns ar e omitted as nothing happens during them):

T1 Alice c asts Infest. Turing processing occurs: a white or

green token dies, a new white or gre en token is c reated.

T2 Alice casts Cleansing Beam, putting two +1/ + 1 c ount-

ers on the side of the tape we are moving away fro m.

T3 If the Turing machine is remaining in the same state, [Annotation 19]

Alice casts Coalit ion Victor y. If it is changing state, Alice casts Soul Snuffers, putting a − 1/ − 1 counter on each creature.

T4 If the Turing machine is remaining in the same state, this

is the point where Alice casts Soul Snuffer s. Otherwise, the next computational step begins.

A. Beginning a Computational Step and Casting Spells

At the beginning of a computational step, it is Alice’s turn and she has the card Infest in hand. Her library consists of the other cards she will cast during the co mputation (Cleansing Beam, Coalition Victory, and Soul Snuffers, in tha t order). Bob’s hand and library are both empty. The Turing machine is in its starting state and th e tape has already been initialised.

At the start of each of Alice’s turns, she has one card in hand. She’s for ced to cast it due to Bob controlling Wild Evocation, which reads “At the beginning of each player’s upkeep, that player reveals a card at random from their hand. If it’s a land card, the player pu ts it onto th e battleﬁeld. Otherwise, the player casts it without paying its mana cost

if able.” When the card resolves, it would normally be put into her graveyard, but Alice is enchanted by Wheel of Sun and Moon, which causes it to be placed at the bottom of her [Annotation 18] library instead, allowing her to redraw it in the future and keeping the cards she needs to cast in order. After her upkeep step, Alice proceeds to her draw step and draws the c ard that she will ca st next turn.

Alice has no choices throughout this process: she do es control one land, but it remains permanently tapped because of Choke (“Islands don’t untap during their con trollers untap steps”), so she is unable to cast any of the spells she draws except via Wild Evocation’s ability. Neither player is able to attack because they both control a Blazing Archon, “Creatures can’t attack you.”

Bob has no cards in hand and controls Recycle, which reads (in par t) “Skip your draw step”. This prevents Bob from losing due to drawing fro m an empty library.

B. Reading the Current Cell

On the ﬁrst turn of the cycle, Alice is forced to cast Infest, “All creatures get − 2/ − 2 until end of turn.” This kills one creature: the tape token at the position of the current read head, controlled by Bob. This will cause prec isely o ne creature of Bob’s to trigger – either a Rotlung Reanimator or a Xathrid Necromancer. Which precise one triggers is b ased on that token’s cre ature type and the machine’s current state, correspo nding to the a ppropriate rule in the deﬁnition of the (2, 18) UTM . This Reanimator or Necromancer will create a new 2/2 token to replace the one that died. T he new token’s creature type represents the symbol to be written to the current cell, and the new token’s colour indicates the direction for the machine to move: white for left or green for right.

Alice controls Illusory Gains, an Aura which reads “You control enchanted creature. Whenever a creature enters the battleﬁeld under an opponent’s control, attach Illusory Gains to that creature.” Each time one of Bo b’s Rotlung Reanimato r s or Xathrid Necromancers creates a new token, Illusory Gains triggers, granting Alice co ntrol of the newest token o n the tape, and reverting contr ol of the previous token to Bob.

4

#### Page 5

TABLE II FULL TEXT OF THE ROTLUNG REANIMATORS AND XATHRID NECROMANCERS ENCODING THE (2, 18) UTM

Rogozhin’s program Card text q 1 1 c 2 Lq 1 Whenever an Aetherborn dies, create a 2/2 white Sliver q 1

−→ 1 ←− 1 1 Rq 1 Whenever a Basilisk dies, create a 2/2 green Elf q 1

←− 1 c 2 Lq 1 Whenever a Cephalid dies, create a 2/2 white Sliver q 1

−→ 1 1 1 Rq 1 Whenever a Demon dies, create a 2/2 green Aetherborn q 1

←− 1 1

−→ 1 1 Lq 1 Whenever an Elf dies, create a 2/2 white Demon q 1 b ←− b Rq 1 Whenever a Faerie dies, create a 2/2 green Harpy q 1

−→ b

←− b 1 Rq 1 Whenever a Giant dies, create a 2/2 green Juggernaut q 1

←− b b Lq 1 Whenever a Harpy dies, create a 2/2 white Faerie q 1

−→ b 1 b Rq 1 Whenever an Illusion dies, create a 2/2 green Faerie q 1

←− b 1

−→ b 1 Lq 1 Whenever a Juggernaut dies, create a 2/2 white Illusion q 1 b 2 b 3 Lq 2 Whenever a Kavu dies, create a tapped 2/2 white Leviathan q 1 b 3

−→ b 1 Lq 2 Whenever a Leviathan dies, create a tapped 2/2 white Illusion q 1 c −→ 1 Lq 2 Whenever a Myr dies, create a tapped 2/2 white Basilisk q 1 −→ c ←− c Rq 1 Whenever a Noggle dies, create a 2/2 green Orc q 1 ←− c −→ c 1 Lq 1 Whenever an Orc dies, create a 2/2 white Pegasus q 1 −→ c 1 ←− c 1 Rq 2 Whenever a Pegasus dies, create a tapped 2/2 green Rhino q 1 ←− c 1 HALT Whenever a Rhino dies, create a 2/2 blue Assassin q 1 c 2

←− 1 Rq 1 Whenever a Sliver dies, create a 2/2 green Cephalid

q 2 1 ←− 1 Rq 2 Whenever an Aetherborn dies, create a 2/2 green Cephalid q 2

−→ 1 ←− 1 Rq 2 Whenever a Basilisk dies, create a 2/2 green Cephalid q 2

←− 1 −→ 1 Lq 2 Whenever a Cephalid dies, create a 2/2 white Basilisk q 2

−→ 1 1

←− 1 1 Rq 2 Whenever a Demon dies, create a 2/2 green Elf q 2

←− 1 1 1 Lq 2 Whenever an Elf dies, create a 2/2 white Aetherborn q 2 b b 2 Rq 1 Whenever a Faerie dies, create a tapped 2/2 green Kavu q 2

−→ b ←− b Rq 2 Whenever a Giant dies, create a 2/2 green H arpy q 2

←− b −→ b Lq 2 Whenever a Harpy dies, create a 2/2 white Giant q 2

−→ b 1

←− b 1 Rq 2 Whenever an Illusion dies, create a 2/2 green Juggernaut q 2

←− b 1

−→ b Lq 2 Whenever a Juggernaut dies, create a 2/2 white Giant q 2 b 2 b Rq 1 Whenever a Kavu dies, create a tapped 2/2 green Faerie q 2 b 3

←− b 1 Rq 2 Whenever a Leviathan dies, create a 2/2 green Juggernaut q 2 c ←− c Rq 2 Whenever a Myr dies, create a 2/2 green Orc q 2 −→ c ←− c Rq 2 Whenever a Noggle dies, create a 2/2 green Orc q 2 ←− c −→ c Lq 2 Whenever an Orc dies, create a 2/2 white Noggle q 2 −→ c 1 c 2 Rq 2 Whenever a Pegasus dies, create a 2/2 green Sliver q 2 ←− c 1 c 2 Lq 1 Whenever a Rhino dies, create a tapped 2/2 white Sliver q 2 c 2 c Lq 2 Whenever a Sliver dies, create a 2/2 white Myr

So at any point Bob controls all of the tape except for the most rece ntly written sy mbol, which is controlled by Alice .

C. Moving Left or Right

If the new token is white, the Turing machine needs to move left. To do this we n eed to take two actions: put a +1/ + 1 counter on a ll white creatures (move the tape away from white), and put a − 1/ − 1 counter on all green creatures (move the tape towards green). We rephrase this instead as: put two +1/ + 1 counters on a ll white creatures, and put a − 1/ − 1 counter on all creatur es.

On Alice’s second turn, she ca sts Cleansing Bea m, which reads “Cleansing Beam deals 2 d a mage to target creature and each other crea ture that shares a color with it.” Bob controls Privileged Position so none of Bob’s creatures can be targeted by any spell Alice casts. Alice controls some creature s other than the tape token, but they have all been gr a nted creature type Assembly-Worker by a hacked Olivia Voldaren, and Alice controls a Steely Resolve namin g Assembly-Worker

(“Creatures of the chosen type have shroud. (They can’t b e the targets of spells or abilities.)”) This makes it so that the only legal target for Cleansing Beam is the one tape token that Alice controls thanks to her Illusory Gains.

Recall that this token is white if we’re moving left, or green if we’re moving right. Cleansing Beam is about to deal 2 damage to ea ch white crea ture if we’re moving left, or to each green creature if we’re moving rig ht. Alice an d Bob each control a copy of Vigor – “If damage would be dealt to another creature you control, prevent tha t damage. Put a +1/ + 1 counter on that creature for each 1 damage prevented this way.” So Cleansing Beam ends up putting two +1/ + 1 counters on eith e r each white cr e ature or each gr e en creature.

On the last tu rn of the cycle, Alice casts Soul Snuffers, a 3/3 black creature which reads “When Soul Snuffers enters the battleﬁeld, put a − 1/ − 1 counter on eac h creature.” Th e re are two copies of Dread of Night hacked to each say “Black creatures get − 1/ − 1”, which mean that the Soul Snuffers’ triggered ability will kill itself, as well as shrinking every other

5

#### Page 6

creature. The creatures comprising the tape have n ow received either a single − 1/ − 1 counter, or two +1/ + 1 counter s and a − 1/ − 1 counter. To ensure that the creatures providing the infrastructure (such as Rotlung Rea nima tor) aren’t killed by the succession of − 1/ − 1 counters each computational step, we arrange that they also have game colours gre en, white, red and black, using Prismatic Lace, “Target permanent becomes the color or colors of your choice. (This effect lasts indeﬁnitely.)” Accordingly, each cycle Cleansing Beam will put two +1/+1 counters on them, growing them faster than the − 1/ − 1 counters shrink them. This applies to each creature excep t Vigor itself; to keep each player’s Vigor from dwindling, there is a Fungus Sliver hacked to read “All Incarnation creatures have ‘Whenever this crea ture is dealt damage, put a +1/ + 1 counter on it.’ ”

D. Changing State

The instruction to change state is handled by replacing seven of Bob’s Rotlung Reanimators with Xathrid Necromancer. These two c ards have very similar text, except that Xathrid Necromancer only notices Bob’s creatures dying (this is not a problem, as the active cell of the tape is always contro lled by Bob), and that Xathrid Necromancer creates its token tapped.

For example, when the q 1 program (State A) sees symbol 1, it writes symbol 18, m oves left, and remains in state A. This is represented by a p hasing Rotlung Reanimator under Bob’s control saying “Whenever Rotlung Reanimator or another Aetherborn dies, c reate a 2/2 white Sliver creature token.”

By contrast, when the q 1 program sees symbol 11, it writes symbol 12, m oves left, and changes to state B. This is represented by a phasing Xathrid Necromancer under Bob’s control saying “Whe never Xathrid Necromancer or another Kavu creature you control dies, create a tapped 2/2 white Leviathan creature token.”

In both cases this token is cr eated under Bob’s control on turn T1, but Alice’s Illusory Gains triggers and grants her control of it. In the case where it’s tappe d, that means at the beginning of turn T2, it will untap. This causes Alice’s Mesmeric Orb’s trigger to be put on the stack at the same time as Bob’s Wild Evocation’s trigger ( sin ce no pla yer receives priority during the untap step). Alice is the active pla yer, so Alice’s tr igger is put on the stack ﬁrst and then Bob’s [16]; so the Wild Evocation trigger resolves, forcing Alice to ca st and resolve Cleansing Beam, before the Mesmeric Orb trigger resolves.

When the Mesmeric Orb trigger does reso lve, it tries to put the Coalition Victory from the top of Alice’s library into her graveyard. But Wheel of Sun and Moon modiﬁes this event to put Coalition Victory onto the bottom of her library, just underneath the Cleansing Beam that’s just resolved.

Once all these triggers are resolved, Alice proceeds to her draw step. When the state is not c hanging, she will draw Coalition Victory at this point, but when the state is changing,

that card is skipped and she moves on to draw Soul Snuffers in turn T2’s draw step, so she will cast it on turn T3.

The net result of this is that the computation step is 3 turns long for each player when the state is changing, but 4 turns long f or each player when the state is not changing. In the normal 4-turn operation, Bob’s p hasing Reanima tors and Necromancers will phase in twice and ph ase out twice , and be in the same state on one cycle’s turn T1 as they were in the previous cycle’s turn T1. But when changing state, they will have changed phase by the next cycle’s turn T1, switching the Turing machine’s state.

E. Out of Tape

The Turing tape can be initialised to a ny desired length before starting processing. But it is preferable to allow the machine to run on a simulated inﬁnite tape: in other words, to assume that any uninitialised tape space contains symbol 3 (the blank symbol in the (2, 18 ) UTM), represented by creature type Cephalid. This is accomplished by having the ends of the currently-initialised tape marked by two special tokens, one green Lhurgoyf and one white Rat. Su ppose we’ve exhausted all the initialised tape to the left. This means that the casting of Infest on turn T1 kills the Lhurgoyf rather than one of the normal tape types. This does not directly trigg er any of the normal Reanimators/Necromancers. Instead, Bob has another Rotlung Re animator hacked to read “Wh e never Rotlung Reanimator or another Lhurgoyf dies, create a 2/2 green Lhurgoyf creature token”, and A lice has a Rotlung Reanimator hacked to read “Whenever Rotlung Reanimator or another Lhurgoyf dies, create a 2/2 black Cephalid creature token.” Bob’s trigger will resolve ﬁrst, then Alice’s.

First, Bob’s Reanimator trigger creates a new Lhurgoyf just to the left of the current head. (Alice’s Illusory Gains triggers and gives her control of this new Lhurgoyf, but that will soon change.) We have one c opy of Shared Tr iumph set to Lhurgoyf (“Creatures of th e chosen type get +1/+1”) so this token arrives as a 3/3.

Second, Alice’s Reanimator trigger now creates a 2/2 black Cephalid under Alice’s control. The same two copies of Dread of Night as before are giving all black cre atures − 2/ − 2, so the black Cephalid w ill arrive as a 0/0 and immediately die.

The death of this Cephalid triggers one of th e regular phasing Reanimators o f Bob’s just as if a tape cell containing symbol 3 had been read: a new 2/2 token is created and Illusory Gains moves to that new token. The green Lhurgoyf token ser ving as an end-of-tape marker has be en recreated one step over to th e left.

The situation for the white Rat representing the right-hand end o f the tape is exactly equivalent. Bob has a Rotlung Reanimator hacked to read “Whenever Rotlung Reanimator or another Rat dies, crea te a 2/2 white Rat creature token”; Alice has a Rotlung Reanimator hacked to read “Whenever Rotlung Reanim ator or another Rat dies, create a 2/2 black Cephalid creature token”; and we have ano ther Shared Triumph set to Rat.

6

#### Page 7

(This algorithm would be a little more complex if reading symbol 3 could cause a state change in the (2, 18) UTM , but thankfully it ca nnot.)

F. Halting

We choose to encode halting as making Alice win th e game. When the Turing machine doesn’t change state, Alice casts the card Coalition Victory on her third turn. It reads “You win the game if you control a lan d of eac h basic land type and a creature of e ach color.” This normally accomplishes nothing because she controls no blue cr e atures (Prismatic Lace has been used to give her creatures of all the other colours). She [Annotation 20] does, however, control one land, and also controls Prismatic Omen, which re ads “L ands you control are eve ry basic land type in addition to their other types.” Recall that Choke is in play, preventing he r from activating the mana ability of this land.

When the halt symbol is read (symbol 17 in state A), the appropriate phasing Reanimator of Bob’s read s “Whenever Rotlung Reanimator or another Rhino dies, create a 2/2 blue Assassin creature token.” Alice’s Illusory Gains takes control of this Assassin token in th e usual way in turn T1. She now meets the condition for Coalition Victory when she casts it on turn T 3, and wins the game.

If the encoded machine does not in fact h a lt then th e game has entered an unbreakable deterministic in ﬁnite loop , which is speciﬁed as a draw by r ule 104.4b [16].

V. DISCUSSION

A. Consequen ces for Computational The ories of Ga m e s

This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature. I n addition to showing that optimal strategic play in Magic is non-computable, it also shows that merely evaluatin g the deterministic consequences of past moves in Magic is non-computable. The full complexity of optimal strategic play remains an open qu estion, as do ma ny other computational aspects of Magic. For example, a player appears to have inﬁnitely many moves available to them from some board states of Magic. Whether or not there exists a

real-world game o f Magic in which a player has inﬁnitely many meaningfully different moves available to them has the potentially to highly impact the way we understand and model games as a form of computation.

Indeed , this result raises several interesting philosophical questions about games as a form of computa tion. Some authors, such as Demaine and Hearn [9], have sought a formal framework for modelling games that is strictly sub-Turing. Unlike the open-world, non-strategic game s in which Turing machines have been constructed be fore, Magic: The Gathering is unam biguously a two-playe r strategic gam e like such models attempt to represen t. Therefore this result shows th a t any sub- Turing model is n ecessarily inadequate to capture all gam es. Quite the opposite: it seems likely that a super-Turing model of game s would be necessary to exp la in Magic. The na¨ıve extension of Demaine and Hea rn’s Constraint Logic to allow for unbounded memory appears to be meaningless, although it’s possible that a clever appr oach would bring success.

Open Problem 3: Does there exist a generalisation of Constraint Logic that explains the computational complexity of Magic: The G athering?

Although our construction is reducible to the Halting Problem, the fact that even evaluating a board is non-computable is strongly suggestive that th e complexity of strategic play is greater than that. We be lieve there is strong evidence that the true computation al complexity is far highe r. In particular, we conjecture:

Conjecture 4: Playing Magic: The Gathering optimally is at least as hard as 0 (ω) . Whether or not it is possible for there to be a real-world game whose computational complexity is strictly harder than 0 (ω) is an interesting p hilosophical question. If not, then this conjecture would imply that Magic: The Gathering is as har d as it is possible for a real-world game to be.

B. Real-world Playab ility a nd Legality

While ther e are practical difﬁculties invo lved with correctly setting up the necessary board state, such as running out of space on y our table, a sufﬁciently tena cious player could set up and execute this construction in a re al-world tournament

TABLE III 60-CARD DECKLIS T TO PLAY THE TURING MACHI NE I N A LEGACY TOURNAMENT

Card Purpose Card Purpose Card Purpose 4 Ancient Tom b Bootstrap 1 Rotlung Reanimator Logic processing 1 Xathrid Necromancer Change state 4 Lotus P etal Bootstrap 1 Cloak of Invisibility Logic processing 1 Mesmeric Orb Change state 4 Grim Monolith Inﬁnite mana device 1 Infest Logic processing 1 Coalition Victory Halting device 4 Power Artifact Inﬁnite mana device 1 Cleansing Beam Logic processing 1 Prismatic Omen Halting device 4 Gemstone Array Inﬁnite mana device 1 Soul Snuffers Logic processing 1 Choke Halting device 4 Staff of Domination Draw rest of deck 1 Illusory Gains Logic processing 1 Recycle Remove choices 1 Memnarch Make token copies 1 Privileged Position Logic processing 1 Blazing Archon Remove choices 1 Stolen Identity Make token copies 1 Steely Resolve Logic processing 1 Djinn Illuminatus Simplify setup 1 Artiﬁcial Evolution Edit cards 1 Vigor Logic processing 1 Reito Lantern Simplify setup 1 Olivia Voldaren Edit cards 1 Fungus Sliver Logic processing 1 Claws of Gix Simplify setup 1 Glamerdye Edit cards 1 Dread of Night Logic processing 1 Riptide Replicator Set up tape 1 Prismatic Lace Edit cards 1 Wild Evocation Forced play device 1 Capsize Set up tape 1 Donate Edit card control 1 Wheel of Sun and Moon Forced play device 1 Karn Liberated Cleanup after setup 1 Reality Ripple Edit card phase 1 Shared Triumph Inﬁnite tape device 1 Fathom Feeder Cleanup after setup

7

#### Page 8

game of Magic: The Gathering. An example 60-card deck that is ca pable of executing this construction on the ﬁrst turn of the game and which is legal in the competitive Legacy format can be seen in Table III.

With the correct d raw, the deck uses Ancient Tomb and three Lotus Petals to play Grim Monolith a nd Power Artifact and generate unlimited colour less mana, at which point Staff of Domination draws the rest of the deck and Ge mstone A rray gene rates unlimited coloured mana. T he deck casts most of the permanents immediately, and uses Stolen Identity to make to ken copies of them (using Memnarch ﬁrst on the en chantments like Cloak of Invisibility). The tape is initialised with Riptide Replicator and Capsize. Dj inn Illuminatus or Reito Lantern allow repeated casting of the text-modiﬁcation card s, as well as Reality Ripple whic h sets the phase of the Rotlung Reanimators and Donate which gives most permanents to Bob. Once everything is set up, Steely Resolve is cast, and then Karn Liberated and Capsize are used to exile all setup permanen ts and all cards from Bob’s han d, eventually exiling Capsize and Karn Liberate d themselves. Now no player has any remainin g choices except to let the Turing machine execute.

In addition to the Comprehensive Rules [16], play at sanctioned Magic: The Gathering tourna ments is also governed by the Tournament Rules [17]. Some of these rules, most notably the ones involving slow play, may effect an individual’s ability to successfully execute the combo due to concerns a bout the sheer amount of time it would take to manually move the tokens ar ound to simulate a computation on a Tu ring machine. This would not be a concern for two agents with sufﬁciently high computational power, a s the Tournament Rules also provide a mechanism called “shortcuts” for players to skip carrying out laborious loops if both players agree on the game state at the beginning and the end of the shortcut.

VI. CONCLUSION

We have presented a methodology for embeddin g Rogozhin’s (2, 18) universal Turing machine in a two-player game of Magic: The Gathering. Consequently, we have shown that identifying the outcome of a game of Magic in which all moves are forced for the r e st of the gam e is undecidable. In addition to solving a decade-old outstanding open problem, in the process of arriving at our resu lt we showed that Magic: The Gathering d oes not ﬁt assumptions commonly made by computer scientists while modelling games. We conjec ture that optimal play in Magic is far harder than this result alon e implies, and leave the true complexity of Magic and the reconciliation of Magic with existing theories of games fo r future research.

ACKNOWLEDGEMENTS

We are grateful to C-Y. Howe for help simplifying our Turing machine constructio n considerab ly and to Adam Yedidia for conversations about the design and construction of Turing machines.

REFERENCES [1] David Auger and Oliver Teytaud. The frontier of decidability in partially

observable recursive games. International Journal of Foundations of Computer Science, 2012. [2] Stella Biderman and Bjørn Kjos-Hanssen. Non-comparable natu-

ral numbers. Theoretical Computer Science Stack Exchange, 2018. https://cstheory.stackexchange.com/q/41384(version:2018-08-16). [3] Krishnendu Chatterjee and Rasmus Ibsen-Jensen. T he complexity of

deciding legality of a single step of Magic: The Gathering. In 22nd European Conference on Artiﬁcial Intelligence, 2016. [4] Alex Churchill. Magic: The Gathering is Turing complete v5, 2012.

https://www.toothycat.net/ ∼ hologram/Turing/. [5] Alex Churchill et al. Magic is Turing complete (the Turing machine

combo), 2014. http://tinyurl.com/pv3n2lg. [6] Peter I. Cowling Colin D. Ward and Edward J. Powley. Ensemble deter-

minization in Monte Carlo tree search for the imperfect information card game Magic: The Gathering. In IEEE Transactions on Computational Intelligence and AI in Games, volume 4, 2012. [7] Michael J. Coulombe and Jayson Lynch. Cooperating in video games?

Impossible! Undecidability of team multiplayer games. In 9th International Conference on Fun with Algorithms, 2018. [8] Erik D. Demaine and Robert A. Hearn. Playing games with algorithms:

algorithmic combinatorial game theory. In 26th Symp. on Mathematical Foundations in Computer Science, pages 18–32, 2001. [9] Erik D. Demaine and Robert A. Hearn. Constraint logic: A uniform

framework for modeling computation as games. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 149–162, 2008. [10] Erik D. Demaine and Robert A. H earn. Games, Puzzles, and Computa-

tion. CRC Press, 2009. [11] Alexander Esche. Mathematical Programming and Magic: The Gather-

ing. PhD thesis, Northern Illinois University, 2018. [12] Eugenio Fortanely. Personal communication, 2018. [13] H. G. Rice. Classes of recursively enumerable sets and their decision

problems. Trans. Amer. Math. Soc., 74:358366, 1953. [14] Yurii Rogozhin. Sm all universal Turing machines. Theoretical Computer

Science, 168(2):215–240, 1996. [15] Colin D. Ward and Peter I. Cowling. Monte Carlo search applied to

card selection in Magic: The Gathering. In CIG’09 Proceedings of the 5th international conference on Computational Intelligence and Games, pages 9–16, 2009. [16] Wizards of the Coast. Magic: The G ath-

ering comprehensive rules, Aug 2018. https://magic.wizards.com/en/game-info/gameplay/rules-and-formats/rules. [17] Wizards of the Coast. Magic: The

Gathering tournament rules, Aug 2018. https://wpn.wizards.com/sites/wpn/ﬁles/attachements/mtg mtr 21jan19 en.pdf.

8

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/magic-the-gathering-is-turing-complete. More annotated papers: https://fermatslibrary.com/llms.txt
