29 | Digest: Magic: the Gathering is Turing Complete (2022)

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 Magic is 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 of Magic such 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)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.

47=40prime?+7prime?48=41prime?+7prime?\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 HHH which determines if another program halts e.g.

(Video) I Built a COMPUTER in Magic: The Gathering

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

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

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

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

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

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

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

But how can we tell that HHH ran forever? That means that H(H)\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.

(Video) Magic: The Gathering - Turing Complete - a Demonstration

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)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)UTM(2,18) has two states {q1,q2}\{ q_1, q_2 \}{q1,q2} where qiq_iqi 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:

{1,1,1,11,11,b,b,b,b1,b1,b2,b3,c,c,c,c1,c1,c2}\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:

f:(boardstate,legalmove)nextboardstate\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 is_legal(move,board_state)\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 green\color{#0C0} \text{green}green to the left of the head, and whitelol\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:

(Video) Turing Completeness with Rah

(n/n),...,(4/4),(3/3),(2/2)head,(3/3),(4/4),...,(n/n)\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)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):

29 | Digest: Magic: the Gathering is Turing Complete (1)

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.

29 | Digest: Magic: the Gathering is Turing Complete (2)

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

29 | Digest: Magic: the Gathering is Turing Complete (3)

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.

29 | Digest: Magic: the Gathering is Turing Complete (4)

(Video) Plus Summa CST300 Final Project - Long Video

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 2n2n2n 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.”

29 | Digest: Magic: the Gathering is Turing Complete (5)

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.”

29 | Digest: Magic: the Gathering is Turing Complete (6)

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.

(Video) 8 bit CPU in Minecraft. Turing complete! (World download

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.
Apr 21, 2021

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? ›

Pokemon TCG

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.

Videos

1. Plus Summa CST300 Final Project - Short Video
(Joshua Hansen)
2. Turing Machine Simulator
(eno cuka)
3. Bit oder Byte? - Turing Complete #0011
(Florentin Streams)
4. The Magic: the Gathering Rules Iceberg explained (part 3 - final)
(Hugh & Morty Productions)
5. Cedric PUNT (watch and learn) MTG for Advanced Players
(MattSperlingMTG)
6. 5. Bitcoin is Turing complete - Bitcoin Aphorisms
(Ryan X. Charles)

You might also like

Latest Posts

Article information

Author: Dan Stracke

Last Updated: 05/29/2022

Views: 6021

Rating: 4.2 / 5 (63 voted)

Reviews: 86% of readers found this page helpful

Author information

Name: Dan Stracke

Birthday: 1992-08-25

Address: 2253 Brown Springs, East Alla, OH 38634-0309

Phone: +398735162064

Job: Investor Government Associate

Hobby: Shopping, LARPing, Scrapbooking, Surfing, Slacklining, Dance, Glassblowing

Introduction: My name is Dan Stracke, I am a homely, gleaming, glamorous, inquisitive, homely, gorgeous, light person who loves writing and wants to share my knowledge and understanding with you.