## Preface

This post aims to summarize the 900 IQ construction of a Turing Machine using Magic: the Gathering (MTG) mechanics described in the paper *Magic: the Gathering* is Turing Complete authored by Churchill, Biderman, and Herrick.

In this paper we show that optimal play in real-world

Magicis at least as hard as the Halting Problem, solving a problem that has been open for a decade. To do this, we present a methodology for embedding an arbitrary Turing machine into a game ofMagicsuch that the first 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 standard size tournament-legal decks, and does not rely on stochasticity or hidden information. Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognizing who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable.

## Embeddings, Universal Turing Machines

Before we jump into the nitty gritty of the construction, we need to define some language to describe Turing Machines and their applications.

- For our (and the authors') purposes, an
**embedding**is an arrangement of a subset of rules of a system such that they simulate the workings of a Turing Machine.

Additionally, we'll define that **Universal Turing Machine** (UTM) is a special kind of Turing Machine which can simulate other Turing Machines. It can perform any computation that any other computer program can perform given the right inputs.

- If you can embed a UTM into a system, it means that your system is capable of simulating any other computer. Furthermore, it means your system can perform any computable task.

A UTM is a Finite State Machine with a read and write head, an infinitely long tape broken up into cells, and a controller. By moving along the tape, reading and writing symbols, a UTM can emulate (or rather, it *is* by definition) a Finite State Machine. These two capacities are sufficient to describe any (non-quantum) computer that we would typically use.

While there are several different configurations of UTMs, this paper employs a specific variety described by Yurii Rogozhin called a $UTM(2,18)$UTM(2,18). The arguments here mean that the UTM has 2 states, and 18 symbols.

- The
**Church-Turing Thesis**states:

a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

running time not withstanding.

## The Halting Problem

- The
**Halting Problem**, proved to be unsolvable in general by Turing states that:

From a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. A general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

One such example of the Halting Problem is **Goldbach's Conjecture** which states that every even whole number greater than 2 is the sum of two prime numbers. Alternatively, every integer can be expressed as the sum of primes. It remains a conjecture since we *cannot* prove that it is true.

$\begin{aligned}47 &= \underbrace{40}_{ \tt{prime?} ❌} + \underbrace{7}_{ \tt{prime?} ✅} \\48 &= \underbrace{41}_{ \tt{prime?} ✅} + \underbrace{7}_{ \tt{prime?} ✅} \end{aligned}$4748=prime?❌40+prime?✅7=prime?✅41+prime?✅7

But can we determine if the program to determine if this conjecture is true ever *halts*?

Consider some program $H$H which determines if another program halts e.g.

$\begin{aligned} H: (A, \bullet) \rightarrow \{True, False\}\end{aligned}$H:(A,∙)→{True,False}

Where $A$A is some other program, and $\bullet$∙ are arbitrary arguments for $A$A. For example, $A$A could be another Turing Machine with arguments which could be symbols on a tape.

Turing proved that such a program $H$H *does not exist*. Suppose you have some other program:

$\begin{aligned} \overline{H}: (A, \bullet) \rightarrow \{True, False\}\end{aligned}$H:(A,∙)→{True,False}

which tells you the *opposite* of $H$H. So, if $H$H is true, and its input program $A$A halts, then $\overline H$H runs forever. But if $H$H does not halt, then $\overline H$H terminates immediately. What would happen if we gave $\overline{H}$H itself as the input:

$\begin{aligned} \overline{H}(\overline{H}, \bullet) = ???\end{aligned}$H(H,∙)=???

- If $\overline{H}$H runs forever on $\overline{H}$H, then $H(\overline{H})$H(H) must have halted
- Otherwise, if $\overline{H}$H halted, then $H$H must have run forever

But how can we tell that $H$H ran forever? That means that $\overline{H}(\overline{H})$H(H) both halted *and* ran forever ⚔️.

Okay, so how does this all come together and what the heck does it have to do with *Magic*?

## Finally, *Magic*

I'd preface this by saying I have not played *Magic* myself since I was at Scout camp nearly a decade ago and I got stomped, here's a 5 minute breakdown of how the game is played.

MTG is a popular, famously complicated tabletop card game. A simple premise of *Magic* is that each card that can be played changes or breaks the initial rules in some interesting way.

There are two basic types of cards:

**Creatures**which have a subtype,*power*/*toughness*stats (ATK/DEF), as well as some flavor text describing the modification of the rules to be enacted once the creature enters play**Land**mana to cast your spells. There are 5 types, or colors, of land

Most cards are spells, playable via the mana available to a player on their turn. Once a card has been used, it becomes tap'd (making it unavailable for the rest of their turn, pending other rules). After a combat interaction, dead creatures go to a graveyard after a stat comparison (*power*/*toughness*).

For the sake of the paper, combat encounters are irrelevant to the UTM, but creatures' stats, which are modifiable by other cards, are the gateway to the central proof.

The authors are trying to embed a UTM into *Magic* to gain access to the halting problem and everything that accompanies it.

They use the aforementioned Rogozhin $UTM(2,18)$UTM(2,18) which is sort of a minimum viable project to simulate *any computer in the world* (non-quantum). Rogozhin's $UTM(2,18)$UTM(2,18) has two states $\{ q_1, q_2 \}${q1,q2} where $q_i$qi is a transition between states involving all or none of the options available to a Turing Machine: read, write, move. Additionally the 18 states are:

$\begin{aligned} \big\{\overleftharpoon{1}, 1, \overrightharpoon{1}, \overleftharpoon{1}_1, \overrightharpoon{1}_1, b, \overleftharpoon{b}, \overrightharpoon{b}, \overleftharpoon{b}_1, \overrightharpoon{b}_1, b_2, b_3, c, \overleftharpoon{c}, \overrightharpoon{c}, \overleftharpoon{c}_1, \overrightharpoon{c}_1, c_2 \big\}\end{aligned}${1,1,1,11,11,b,b,b,b1,b1,b2,b3,c,c,c,c1,c1,c2}

All these don't really matter, the point is that we can represent them using *Magic* cards.

It's important to note that some games are obviously Turing Complete, like Minecraft. However, MTG is *notably* not intentionally Turing Complete.

Now, the authors assert that it is possible to compute the *next* board state given the current board state and a legal move:

$\begin{aligned} f: (\text{board state, legal move}) \rightarrow \text{next board state}\end{aligned}$f:(boardstate,legalmove)→nextboardstate

However, given the nature of MTG, there is no trivial $\tt is\_legal(move, board\_state)$is_legal(move,board_state) function or check. The authors acknowledge that previous work has shown that, working cooperatively (and making known, legal moves), players can construct a Turing Machine, but it is far more interesting to show that in a limited, competitive game, it is not possible to predict how a game will end.

## Construction

The authors introduce our two arch-nemeses: Alice and Bob along with the 3 elements of a Turing Machine that need to be mapped to the game of Magic: the tape, controller, and read/write head.

The tape is intuitively challenging to embed since there are no geometric or physical metrics present in the game. All we have in a game of *Magic* are stats, counters, modifiers, etc.

Nonetheless, *lots* of creatures, organized by color (with $\color{#0C0} \text{green}$green to the left of the head, and $\overbrace{\color{#FFF}\text{white}}^{lol}$whitelol to the right) yields a directional notation.

The origin of the tape starts is a Rotlung reanimator (2/2) and the read/write head of the Turing Machine is *lethal* as, in order to traverse the tape, it must slay a creature.

Expanding outwards in either direction from the 2/2 origin are 3/3, 4/4, ..., n/n creatures. The board might look something like this:

$\begin{aligned} \color{#0C0} (n/n) , ... ,(4/4), (3/3), \color{#000} \underbrace{(2/2)}_{head}, \color{#BBB} (3/3), (4/4), ..., (n/n)\end{aligned}$(n/n),...,(4/4),(3/3),head(2/2),(3/3),(4/4),...,(n/n)

The authors select 18 creature types to correspond to Rogozhin's $UTM(2,18)$UTM(2,18) symbols. Notably, each of these 2/2 creatures spawns a another one of the 18 symbolic creatures upond death. (NATO hates them, check out how these three computational theory researchers destroyed the standard phonetic alphabet):

The authors map the controller using black cards, like the Rotlung Reanimator whose flavor text reads:

Whenever Rotlung Reanimator or another Cleric is put into a graveyard from play, put a 2/2 black Zombie creature token into play.

this card represents the origin of the board.

Some cards, like Artificial Evolution modify the text of other cards, for example: duplicate the Rotlung Reanimator, and modify its flavor text:

Using a slew of other cards, the authors demonstrate how it is possible to map the 3 key properties of UTM: a read/write head, a tape, and the ability to change state via the controller.

Computation begins as follows:

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 computation (Cleansing Beam, Coalition Victory, and Soul Snuffers, in that order). Bob’s hand and library are both empty. The Turing machine is in its starting state and the tape has already been initialized.

When Alice casts Infest (-2/-2) it kills all 2/2 creatures which, as we noted above, is just the origin of our tape (which happens to belong to Bob, RIP).

This kills one creature: the tape token at the position of the current read head, controlled by Bob. This will cause precisely one creature of Bob’s to trigger – either a Rotlung Reanimator or a Xathrid Necromancer... This Reanimator or Necromancer will create a new 2/2 token to replace the one that died. The 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.

Upon casting Infest, the center card at the head of the tape dies, but in order to traverse the tape, we must add a +1/+1 and -1/-1 buff and debuff respectively to the current and adjacent creature in order to move, as well as all $2n$2n other creatures on either side as well...

This is cleverly accomplished by modifying creatures of a specific color.

On Alice’s second turn, she casts Cleansing Beam, which reads “Cleansing Beam deals 2 damage to target creature and each other creature that shares a color with it.”

On the last turn of the cycle, Alice casts Soul Snuffers, a 3/3 black creature which reads “When Soul Snuffers enters the battlefield, put a −1/−1 counter on each creature.”

To ensure that the creatures providing the infrastructure (such as Rotlung Reanimator) aren’t killed by the succession of −1/−1 counters each computational step, we arrange that they also have game colours green, white, red and black, using Prismatic Lace, “Target permanent becomes the color or colors of your choice. (This effect lasts indefinitely.)” Accordingly, each cycle Cleansing Beam will put two +1/+1 counters on them, growing them faster than the −1/−1 counters shrink them.

In this way, Cleansing Beam and Soul Snuffer effectively facilitate the movement of the head across the tape.

The full construction includes details about several other cards which Alice and Bob possess in order to maintain the infrastructure prevented, but the embedding is hopefully clear at this point.

Using almost entirely arbitrary information present with MTG, along with Rogozhin's UTM(2,18) in order to "compute" a program , the authors showed that the outcome of a game of *Magic* is non-computable. this is accomplished by importing everything we described about the Halting problem earlier.

It's important to distinguish between the outcome being simply non-deterministic versus non-computable. Non-deterministic outcomes *are* computable (albeit hindered by combinatorically exploding possibilities), whereas the outcome here is **not even in principle a question that we can ask in a way that makes it computable**.

## FAQs

### Is Magic The Gathering Turing-complete? ›

So Churchill et al. have successfully demonstrated that **Magic is accidentally Turing complete**. Programming languages are Turing complete, along with HTML/CSS, PostScript, and PowerPoint.

### What means Turing-complete? ›

Practically, what you need to know is that a Turing-complete language (also called a universal language) is **one where you can compute anything that any other computational method can compute**. In other words, a language that's non-universal—or Turing incomplete—has some limits on the set of things that it can compute.

### Is Pokemon TCG Turing-complete? ›

(Pokemon Yellow)

Turns out **the game logic itself is Turing-complete** in the sense that you can write assembly by filling the player inventory appropriately.

### Which is more complicated Magic or Yugioh? ›

There is a way to play one game of Yu-Gi-Oh with multiple players, but the way MTG sets it up is much less complicated to learn. So if you ever wondered which game would be better to play with multiple players, **MTG takes the cake**, as the system and rules it has feel much more solid overall.

### How complex is MTG? ›

His team has measured the computational complexity of the game for the first time by encoding it in a way that can be played by a computer or Turing machine. “This construction establishes that Magic: The Gathering is **the most computationally complex real-world game known in the literature**,” they say.

### Is Magic The Gathering a computer? ›

I Built a COMPUTER in Magic: The Gathering - YouTube

### What is Turing complete example? ›

In computer science, Turing completeness is a classification for a system of rules that manipulate data. It is named after computer scientist Alan Turing, inventor of the Turing machine. For instance, **programming languages and CPU instruction sets** are examples of formal rule systems that access and modify data.

### How do you know if something is Turing complete? ›

Typically, one proves a given language is Turing-complete by **providing a recipe for translating any given Turing machine program into an equivalent program in the language in question**. Alternately, one can provide a translation scheme from another language, one that has already been proven to be Turing-complete.

### How do you prove something is Turing complete? ›

To prove that a language or device is Turing Complete all you have to do is **show that it can be used to implement a Universal Turing machine**. A language that has a default flow of control, conditional execution and repetition is Turing Complete with only minor additional requirements.

### Is MTG harder than chess? ›

While chess algorithms can handily defeat the best human players in the world, we're still very, very far from actually solving chess. been found to have non-trivial complexity, including Dots-and-Boxes, Jenga, and Tetris. **Magic the Gathering, as it turns out, is more complex than all of them**.

### Is PowerPoint Turing complete? ›

**Some games and other software are Turing-complete by accident, i.e. not by design**. Software: Microsoft Excel. Microsoft PowerPoint.

### Is Doom Turing complete? ›

Analog computers are a type of calculator, and **generally are not Turing complete**. So they can't run Doom. Now, you can build analog computers that are Turing complete, and those can run doom. But not the Antikythera mechanism.

### What is the hardest trading card game? ›

Magic: The Gathering is a popular and notoriously complicated trading card game that pits players against each other, placing them in the role of wizards who do battle with the help of spells, magical artifacts and mythical creatures.

### Why MTG is more popular than Yu-Gi-Oh? ›

Overall, the MTG designers at Wizards of the Coast have done a fantastic job in designing cards that are beginner-friendly. There are other reasons why MTG is much better than Yu-Gi-Oh! other than just card design: **Better art, more compelling lore, and more balanced gameplay**.

### Is MTG skill based? ›

When players have low skill, the games depend more on skill (because both players make errors, a skillful play will have a large impact on the game). And obviously, **when there's a large skill gap, the games are decided based on skill**.

### Why is MTG so complicated? ›

In other words, **there are so many non-trivial decisions that Magic players must make during the process of a game that an algorithm is not capable of determining the perfect strategy**. That makes it more complex than other real-world games with non-trivial complexity, including Jenga and Tetris.

### What is the world's most complex game? ›

**Chess**. One of the most famously difficult games in the world to master is chess.

### Is MTG pay to win? ›

The definition of Pay to Win is where someone can buy gear or items in a game that progress the player at a faster rate, and makes the game largely unbalanced, even for people who have skill in the game without paying. By this definition, the answer is No. **Magic Arena is no more pay to win than paper magic is**.

### How many MTG cards exist? ›

There are currently **more than 20,000** unique Magic cards, to which hundreds are added each year. Cards are sold in a variety of languages and products, including booster packs and preconstructed theme decks.

### Is MTG hard to learn? ›

**It's very easy to learn how to play Magic: The Gathering**, as you can start with simple pre-made card sets before advancing onto making your own deck.

### Is Scratch Turing complete? ›

With these features, Scratchers can create algorithms, or instructions to complete specific tasks. Computer scientists would say **Scratch is a Turing-complete programming language**, which means it can perform all the basic functions that make up algorithms.

### Is Game of Life Turing complete? ›

This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints; **it is Turing complete**.

### Is the human brain Turing complete? ›

In the extreme case a human brain could be nothing but a device which mindlessly produces all possible algorithms. One can in fact build a machine which does this, but **this machine would not be Turing complete**.

### What isn't Turing complete? ›

A Turing machine can make decisions based on what it sees in memory - **The 'language' that only supports + , - , * , and / on integers** is not Turing complete because it can't make a choice based on its input, but a Turing machine can.

### Is Idris Turing complete? ›

**Idris is Turing Complete**! It does check for totality (termination when programming with data, productivity when programming with codata) but doesn't require that everything is total. Interestingly, having data and codata is enough to model Turing Completeness since you can write a monad for partial functions.

### Is Bitcoin Turing complete? ›

We have empirically demonstrated that any Turing machine can be simulated on Bitcoin and thus **definitively proven it is Turing-complete¹**.

### What is Turing theory? ›

The thesis states that Turing machines indeed capture the informal notion of effective methods in logic and mathematics, and provide a model through which one can reason about an algorithm or "mechanical procedure". Studying their abstract properties yields many insights into computer science and complexity theory.

### Is the universe a Turing machine? ›

**The Universe Is a Giant Abstract Turing Machine** That Doesn't Need to Be Run. If U() is the set of all possible Turing machine definitions, U(a) is just one of them, one that represents ours. This philosophy is also termed digital physics, and this essay attempts to put the philosophy in layman's term.

### Why is it called the Turing test? ›

The Turing Test is a method of inquiry in artificial intelligence (AI) for determining whether or not a computer is capable of thinking like a human being. **The test is named after Alan Turing**, the founder of the Turing Test and an English computer scientist, cryptanalyst, mathematician and theoretical biologist.

### Does Magic: The Gathering make you smarter? ›

**Magic also makes you smarter personality-wise**. Whilst games can be very drawn out and seem to take a lot of mental investment, it teaches you to be gracious in defeat as, after all, it is just a game.

### What is the most complex strategy game? ›

**The 10 Hardest RTS Games Ever Made, Ranked**

- 8 Company Of Heroes.
- 7 Distant Worlds.
- 6 Take Command - 2nd Manassas.
- 5 Sudden Strike.
- 4 Command & Conquer: Tiberian Dawn.
- 3 Commandos: Behind Enemy Lines.
- 2 StarCraft II: Wings of Liberty.
- 1 Aurora 4x.

### Who is the greatest bridge player of all time? ›

Bridge. The greatest player in the world—perhaps the greatest player of all time—is a seemingly unremarkable, quietly intense septuagenarian from Dallas named **Bob Hamman**.

### Is Excel Turing complete? ›

With the addition of custom functions that can call each other and recursively call themselves, **Excel's formula language becomes Turing-complete**, effectively meaning that Excel users can compute anything without resorting to another programming language.

### Is JavaScript Turing complete? ›

Now if you think about any modern programming language, they also take programs(written by us) as input and run them. Further, any program that can be theoretically written to run for a Turing machine can also be written in JavaScript. Thus, **JavaScript is Turing complete**. That's it!

### Is SAS Turing complete? ›

SAS tried to claim that SAS was not a programming language, because **the PROC steps are not Turing complete**. They knew that a programming language was not copyrightable.

### Is iPhone Turing complete? ›

There is a killer argument which shows that the iPhone, like any other computer, is **not Turing-complete**: it only has a finite amount of memory. Therefore, the class of computing power is that of a finite automaton, no more.

### Is Ocarina of Time Turing complete? ›

**It's turing complete by design**, and it can and is sandboxed to a lot of success.

### Are pdfs Turing complete? ›

With no recursion and no unbounded loops, **PDF is clearly not Turing complete**.

### What is the number 1 trading card game in the world? ›

Since making its debut in 1993, the **Magic: The Gathering** trading card game (TCG) has spread across the world. According to the publishers Wizards of the Coast, Inc (USA) – a subsidiary of Hasbro – the game is now played globally by an estimated 20 million-plus players.

### What is the most popular TCG in the world? ›

**Vanguard** has regularly been voted a top choice TCG, and that hasn't changed in 2022.

### What is the best selling trading card game? ›

### Is Yu-Gi-Oh complicated? ›

Yu-Gi-Oh doesn't have a resource system so the cards themselves have to act as resources. This means that **the card designers have to add a lot of the complexity to the card text itself such as restrictions and costs which make them more complicated.**

### Is Yu-Gi-Oh similar to Magic: The Gathering? ›

Yu-Gi-Oh! and MTG are not just card games, like poker or blackjack or bridge. They are trading card games, with each having thousands of unique cards with different effects and different gameplay utility, depending on the deck. A player may have a dire need for some cards and absolutely no need for others.

### Is Yu-Gi-Oh better than Pokemon? ›

It is more fun, easier to play, and more social in nature than its main competitor, Yu-Gi-Oh. From a collector's standpoint, **Pokemon is also more viable**, with plenty of older cards holding up their value even today, with the majority of cards in Yu-Gi-Oh only being valuable based on the current meta.

### Is Yu-Gi-Oh still popular? ›

**Yugioh is still crazy popular**, seemingly even more-so than Magic, Pokemon, or whatever. There are constantly Yugioh tournaments going on at a local comic store.