<p>Ok, I have a solution that avoids the mana burn issue I ran into. This is kind of a hack, since I need to make the assumption that players can identify specific lands, which I don't think is dealt with in the rules. In practice this is the case, since they can be arranged in a line based on the order in which they are played.</p>

<p>First, the full description of the problem from the Draw3Cards site:</p>

<blockquote>
  <p>A positive answer would be composed of
  these components:</p>
  
  <ol>
  <li>A computable function fM from Turing Machines to ordered Magic decks
  (where the order of the library
  matters)</li>
  <li>Two well defined deterministic &amp; computable strategies to play Magic
  (that do not depend on the deck).
  Let's call them Strategy TS (Turing
  Strategy) and Strategy IS (Input
  Strategy).</li>
  <li>A computable way fI to encode any string of zeros and ones as a
  Magic Input deck. One such way would
  be to take the Gödel number of the
  string and put as many islands in the
  Input deck.</li>
  </ol>
  
  <p>The additional condition that should
  be satisfied is this: Given a Turing
  Machines TM, let us consider the
  result of the Magic game between
  strategy TS playing with deck fM(TM)
  against strategy TI playing with deck
  fI(I), when the libraries are not
  shuffled before the game starts. This
  game should be won by the first player
  if and only if TM(I) = true.</p>
</blockquote>

<p>So here is the idea. We have 2 players, A and B. B will supply the input, while A will directly implement a Turing machine. The decks will be composed almost entirely of land, but also the <a href="http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=50150" rel="noreferrer">Gemstone Array</a> card to void mana burn. A will have 3 types of land: Islands, Mountains and Forests. The basic idea is to use tapped land to represent a 1 and untapped land to represent a 0. Islands will be used to represent the state of the tape, Mountains to index the current position along the tape and Forests to represent the internal state of 24 state 2 symbol Turing machine (I believe there is a universal one due to Rogozhin).</p>

<p>The decks are ordered as follows:
A's deck: Gemstone Artifact; 6 Forests (since $2^5 = 32 > 24$ plus an additional forest); For m=0 to infinity: $2^{m+1}$ Islands followed by 1 Mountains. Note that the number of mountains (which can be either tapped or untapped) is always the number required to index every island, plus a halting state.</p>

<p>B's deck: Gemstone Artifact; 6 Forests (since $2^5 = 32 > 24$ plus an additional forest); For m=0 to infinity: $2^{m+1}$ Input Lands followed by 1 Mountains. Note again that the number of mountains (which can be either tapped or untapped) is always the number required to index every island held by A, plus a halting state. The Input lands are taken to be Plains (to represent a 0 in the input string), Swamp (to represent a 1 in the input string) and Islands (which are used after the end of the input string has been reached.</p>

<p>Strategy:
A and B both play one land a turn in the order in which they are drawn. 
When each has drawn 4 forests they play Gemstone Artifact.
Note A goes first, so already has an Island when B draws plays his first input card.</p>

<p>A and B simply continue to place their cards in order until B has exhausted their Plains and Swamps and plays their first Island. On his next go, A for all i taps his ith Island iff Bs ith Input Land was a swamp. A initialises his turing machine by tapping his first Forest and Mountain. If he has tapped an odd number of cards he taps his extra forrest, and uses all this mana to add tokens to Gemstone Array. From here on the play proceeds as follows: B uses their turn to simply mirror the state of A's mana. B taps his ith Input Land iff A's ith Island is tapped. Similarly B taps his ith Forest(Mountain) iff A's ith Forest(Mountain) is tapped. As A always taps an even number of cards, so does B, and the mana is used to add tokens to Gemstone Array. </p>

<p>On A's turn, all of A's mana becomes untapped, so A looks at the state of B's mana, represents the state of A's mana on the previous turn. A applies the transition rule according to the universal (24,2) machine to B's state to obtain his new state.</p>

<p>Play proceeds in this manner until the turing machine halts. At this point, A puts his mountains into the reserved "finished" state (the all untapped state). If the Turing machine halted in an accepting state, B copies the state of A's mountains, but taps all their remaining land neglecting to use Gemstone array, thus beginning the process of suicide by mana burn. On A's turn, if B's mountains are in the "finished" state, and all B's other land is tapped, A simply does nothing (note that his mountains are automatically in the "finished" state). If A's mountains are in the finished state, but nothing else is tapped, B continues suicide by mana burn. This is repeated until B is dead.</p>

<p>If however, the machine finishes in the reject state, B leaves all their cards untapped. If all B's cards are untapped, A taps all his cards, beginning the same process of suicide by mana burn. If A's non-Mountain cards are all tapped, and the mountains untapped, B leaves all their cards untapped. This will lead A to continue the mana burn suicide until he loses the game.</p>

<p>This should satisfy the criteria asked for in the question, and hence when this ordering is allowed, I believe the game is Turing complete in the sense described in the question.</p>

CC BY-SA 2.5
2010-10-09T15:15:20.583Z
Cool. An extra thought: As long as any player taps more than 1 land per turn, you can use charges on the Gemstone Array to avoid mana burn. For example, if I need to tap 3 lands, I turn two mana into a charge, spend the charge to generate one mana, then spend the two remaining mana to create a new charge. -- of course, you solved this problem already anyway. :)
Daniel Apon
CC BY-SA 2.5
2010-10-09T15:30:32.747Z
Actually, it just occurred to me that you could use a universal cellular automata instead with the same techniques, but that this would cut down on the number of different types of land required.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-09T15:54:49.490Z
Aewsome!  It might also be easier to simulate a 2-counter machine (using different types of mana as the counters) instead of directly simulating a Turing machine: http://en.wikipedia.org/wiki/Counter_machine#Two-counter_machines_are_Turing_equivalent_.28with_a_caveat.29
Jeffε
CC BY-SA 2.5
2010-10-09T15:56:43.280Z
Your reduction also implies that (cooperative) Magic with a finite number of cards is PSPACE-hard.
Jeffε
CC BY-SA 2.5
2010-10-09T16:14:36.357Z
Does that follow? I believe the game ends if either player runs out of cards. There may be a card which can be used to circumvent this by recycling graveyard cards.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-09T16:42:55.503Z
@Joe - there is no longer mana burn in Magic. You could use Platinum Angel to avoid losing due to running out of cards in your graveyard.
ripper234
CC BY-SA 2.5
2010-10-09T17:09:36.250Z
Well mana burn can easily be removed by adding a creature to each deck as the second card to be held until the TM halts, at which point if it is in an accepting state A summons the creature, otherwise B does. Whoever has a creature in play simply repeatedly attacks until their opponent is dead.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-09T19:29:32.217Z
@Joe, another minor aside: If a player ever recognizes a accepting/rejecting state on the board, it is a legal move in Magic to simply concede on the spot (or do nothing and let the opponent concede). In fact, the language in the official rules seems to suggest that the "right to concede, anytime" is the sole inalienable right in any Magic game. (Although, maybe this isn't as elegant as causing an actual winning/losing condition to occur in-game.)
Daniel Apon
CC BY-SA 2.5
2010-10-09T20:30:00.327Z
I am still missing one thing - you have not provided a way, given a finite deck for player A, to do calculations that require arbitrary size. The amount of lands you have can have in play is finite, so there must be a flaw in your proof sketch.
ripper234
CC BY-SA 2.5
2010-10-09T20:35:28.610Z
However, that should be easy to circumvent: http://draw3cards.com/questions/2860/how-do-you-create-an-arbitrary-number-of-lands-that-last-for-the-next-turn
ripper234
CC BY-SA 2.5
2010-10-09T20:38:21.390Z
@Joe - you missed my comment earlier that the concept of mana burn has been completely removed from the rules. You can fix it by having each player have a copy of Fireball in his deck.
ripper234
CC BY-SA 2.5
2010-10-09T22:33:04.503Z
@ripper234: I didn't miss it. See my comment above about including a creature to deal damage. Also, I am not sure what you mean about the land being finite. At any step i there will be i land in play, but since I don't know when the Turing machine halts, I need an infinite deck.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-09T22:35:58.267Z
@ripper234: I assume the platinum angel rule only applies when it is alive? Otherwise the computation never halts. But in that case, I believe the addition of it would indeed allow for JeffE's corollary, provided you also include a way to kill it.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-10T06:46:28.073Z
@Joe - You can't have an infinite deck for player A. His deck is fixed as the "algorithm" deck. Player B's deck can also not be infinite - his deck represents some finite input. You can create an infinite (well, arbitrarily high) number of land tokens if you need. Yes, Platinum Angel only works when it's alive.
ripper234
CC BY-SA 2.5
2010-10-10T06:53:43.677Z
Also, see @Alextfish's solution on Draw3Carsd: http://draw3cards.com/questions/2851/is-magic-turing-complete/2866#2866
ripper234
CC BY-SA 2.5
2010-10-09T15:01:27.567Z
2010-10-09T15:01:27.567Z
Joe Fitzsimons
<p>Alex Churchill, Stella Biderman and Austin Herrick published <a href="https://arxiv.org/abs/1904.09828" rel="noreferrer">this paper</a> showing that Magic is Turing Complete</p>

<blockquote>
  <p>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, solving a problem that has been open for a decade [1], [10]. 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 recognising who will win a game in which neither 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 unified computational theory of games and remarks about the playability of such a board in a tournament setting.</p>
</blockquote>

CC BY-SA 4.0
2019-06-17T22:14:08.833Z
2019-06-17T22:14:08.833Z
DerMolly
<p><a href="https://cstheory.stackexchange.com/users/1713/alexc">Alex Churchill (@AlexC)</a> has posted a solution that does <em>not</em> require cooperation between the players, but rather models the complete execution of a universal Turing machine with two states and 18 tape symbols.  For details, see  <a href="https://www.toothycat.net/~hologram/Turing/" rel="noreferrer">https://www.toothycat.net/~hologram/Turing/</a> [<a href="http://archive.is/xbCak" rel="noreferrer">archive</a>].</p>

CC BY-SA 3.0
2013-10-29T14:08:18.807Z
The link is dead for me. Should we recreate the solution in the answer to be complete?
Artem Kaznatcheev
CC BY-SA 4.0
2018-06-21T16:05:47.333Z
The solution is being hosted at https://www.toothycat.net/~hologram/Turing/ for the moment.
AlexC
CC BY-SA 4.0
2010-11-09T17:58:12.903Z
2018-06-22T12:13:57.983Z
2018-06-22T12:13:57.983Z
Jeffε
<p>A very specific question, I'm aware, and I doubt it will be answered by anyone that isn't already familiar with the rules of Magic. Cross-posted to <a href="http://draw3cards.com/questions/2851/is-magic-turing-complete">Draw3Cards</a>. Here are the <a href="http://www.wizards.com/magic/comprules/MagicCompRules_20101001.txt">comprehensive rules for the game Magic: the Gathering</a>. See <a href="http://draw3cards.com/questions/2852/an-online-list-of-all-magic-cards">this question</a> for a list of all Magic Cards. My question is - is the game Turing Complete?</p>

<p>For more details, please see <a href="http://draw3cards.com/questions/2851/is-magic-turing-complete">the post at Draw3Cards</a>.</p>

CC BY-SA 2.5
2010-10-09T11:08:55.677Z
(1) What is the input?  Do you assume that you know the content and the order of the cards in both players’ decks?  (2) To analyze its complexity, a problem must have infinitely many possible inputs.  For example, we cannot say that chess is EXP-complete (even if we say so, it means that the generalization of the chess to an n×n board is EXP-complete).  How do you generalize the game?  (3) The game may be too complicated to analyze its complexity, but I do not know.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-09T11:10:31.103Z
@Tsuyoshi, RE (2): There is (explicitly) no maximum deck size in M:TG -- that's one of the first things I checked for. [Edit] Also, RE (1): Though you could know the content of players' decks, the order of the cards is explicitly randomized...
Daniel Apon
CC BY-SA 2.5
2010-10-09T11:13:35.043Z
@Daniel: Thanks.  In fact I checked it too, but I was not sure if anyone wants to analyze the game where each card except for land cards are restricted to at most 4 copies and only the number of land cards can grow.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-09T11:27:13.857Z
For the game to be Turing-complete, you cannot be able to decide the Halting Problem on it. Even though there are a large number of cards, there are still only finitely many. If you restrict occurrences of each (modulo land cards), it may be possible, at some point, to decide whether you've entered an infinite loop by counting non-land cards.
Daniel Apon
CC BY-SA 2.5
2010-10-09T11:44:04.910Z
@Daniel: Not sure if the logic works that way because there are several different types of land cards.  After all, the original game itself may be complicated enough to be Turing complete.  What I am not sure is whether the asker really wants to analyze the game where almost all cards in a deck are necessarily land cards.  I will wait for the asker to reply.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-09T12:01:24.737Z
@Tsuyoshi, you're correct; good catch. As an aside, the asker's link to the other version of the question on Draw3Cards specifies the problem more exactly. I was considering some type of contrived solution involving decks of only land cards (after considering your response) and strategies that would very obviously simulate Turing machine operations, but he wants something that very much looks like an actual game being played.
Daniel Apon
CC BY-SA 2.5
2010-10-09T12:16:24.670Z
As I see it, there are two possible questions here: 1) Is the game Turing complete when played adversarily (in which case it almost certainly isn't) and 2) is it Turing complete when played collaboratively (in which case it almost certainly is). If case 2 is actually also of interest, then I believe I can post an answer.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-09T12:25:55.727Z
@Joe, I say post your answer! :)
Daniel Apon
CC BY-SA 2.5
2010-10-09T13:18:20.110Z
Eek... seems I spoke too soon. The Mana Burn rule keeps breaking my strategy.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-09T13:28:38.920Z
Wow, I wasn't aware there were so many Magic players here :) Please see the version on Draw3Cards for more clarifications. @Joe - I mean your second question.
ripper234
CC BY-SA 2.5
2010-10-09T13:32:33.043Z
@Daniel - For simplicity, I allow the decks not to be shuffled before a game starts - although it might be possible to build a deck that has enough tutors and library-arranging effects to work around this limitation.
ripper234
CC BY-SA 2.5
2010-10-09T13:42:09.850Z
@ripper234, I wouldn't say I'm a Magic player -- I played the game as a kid, but I haven't even thought of it for over a decade now (alas, to not grow older!). A quick question while you're here: It seems like Tsuyoshi and I both have inklings of ideas for how to simulate TMs under restrictions that would seem extremely odd to a non-TCS Magic player, but these seem like duds for answering what you're really asking -- could you give some examples of types of restrictions under which you'd still find the problem interesting? [And maybe update the original question with these thoughts]
Daniel Apon
CC BY-SA 2.5
2010-10-09T13:45:31.447Z
@Joe, does it help if you allow players' lives to be a function of the input size (presumably the deck size)?
Daniel Apon
CC BY-SA 2.5
2010-10-09T14:22:47.907Z
@Daniel - I don't quite follow. Most restrictions would make solving the problem harder, not easier. Regarding your comment on HP and a finite number of cards, there are infinite combos in Magic, and one can create copies of cards, so in a way Magic has 'infinite scratch-space'. I think that a TM can be simulated even within the restriction of using a finite (small) number of non-land cards which are limited to 4 copies.
ripper234
CC BY-SA 2.5
2010-10-09T14:57:44.710Z
@ripper234, an example of the type of restriction I have in mind is highlighted in Joe's comment earlier: Suppose we restrict the players to playing cooperatively. In this case, you could enforce arbitrary strategies on the players in order to simulate a TM, but it wouldn't look like a game of Magic at all; it would look like a TM represented by Magic cards. Or suppose we further restrict the legal input decks to land cards of only two types (representing 0 and 1) -- then it gets even easier to simulate a TM, but now it DEFINITELY doesn't look like a game of Magic.
Daniel Apon
CC BY-SA 2.5
2010-10-09T15:06:51.690Z
The original question actually asks for an ordering of the cards too. I can't deal with shuffling yet.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-09T15:43:58.550Z
@Daniel: That's not a reasonable objection!  Most hardness reductions for games output something that looks more like the reduction than the original game.  (Hamiltonian cycles don't naturally arise in draughts, for example.)
Jeffε
CC BY-SA 2.5
2010-10-09T16:00:47.570Z
@Joe: Why do you think the adversarial game is "almost certainly not" Turing complete?  To simplify the question: Do you think it's decidable whether one player can win in a single turn?
Jeffε
CC BY-SA 2.5
2010-10-09T16:29:20.913Z
Yes. Given that there are a finite number of non-mana cards in even an infinite deck, I think it becomes relatively easy to decide. Further for large shuffled decks the probability of drawing anything other than land is so small the first to draw a useful card will almost surely win.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-09T19:25:42.193Z
@JeffE, it definitely wasn't an objection! Let's just say "personal caution." :) In light of Joe's beautiful answer (that he posted minutes after that comment of mine), my worries were obviously silly.
Daniel Apon
CC BY-SA 2.5
2010-10-09T21:23:24.813Z
I read [your other post](http://draw3cards.com/questions/2851/is-magic-turing-complete) (but please include the specification of the question in the question itself, not just a link to it).  I cannot see how the question is related to Turing completeness of a game.  More precisely, I cannot come up with a specific problem L such that this question can be interpreted as asking whether L is Turing complete or not.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-09T22:29:43.723Z
@Tsuyoshi: I think what the OP was asking for was a specific strategy for the two players, such that deciding who wins when these strategies are used is equivalent to simulating a universal Turing machine, where the input deck encodes the input.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-09T22:56:01.603Z
@Joe: Thanks for the comment, and I stand corrected: I knew that the question is _related_ to the notion of Turing completeness.  However, I do not think that it is correct to say that the game is Turing complete based on the answer to this question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-10T00:30:56.573Z
@Tsuyoshi: Yes, I know what you mean. That is why I phrased my the last sentence of my answer the way I did.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-10T06:44:08.313Z
@Tsuyoshi, @Joe - this is not what I meant in the question. I meant to ask whether "Magic as a computation device" has power equivalent to a TM. I tried to define what "Magic as a computation device" means on Draw3Cards. If my definition isn't clear and you can help me revise it, that'd be great.
ripper234
CC BY-SA 2.5
2010-10-10T11:23:43.923Z
The issue is not that your definition is unclear, but that it is different from what is usually referred to as “a game as a computational device.”  Usually, the complexity of a two-player game refers to the complexity of deciding the winner (or finding the best move for the winner) of a given configuration, assuming that both players play optimally.  In this question, the strategies of both players are also given as part of input, and the only restriction is that the Turing machine and its input must be encoded separately.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-10T11:24:14.430Z
(cont’d)  This question is about simulating Turing machine by a game in a specific sense, and therefore it is morally related to the notion of Turing completeness.  However, I find the title “Is Magic: the Gathering Turing complete?” rather misleading.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-10T13:20:51.723Z
@Tsuyoshi: I'm not entirely sure that playing optimally is well defined for Magic. In principle you don't know what cards are in your opponents deck until you see them played. I don't simply mean the ordering, I mean the actual cards. In this case it seems hard to formulate a strategy which is both effective and independent of your opponents deck.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-10T13:31:29.583Z
@Joe: I agree.  If the content of the opponent’s deck is not known (even as a probability distribution), it is probably impossible to define what it means by “play optimally.”
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-10T14:03:56.873Z
@Tsuyoshi: Yes. Actually, even if the probability distribution were given, it might still be insufficient, as there is no limit on deck size, so you could wind up with something like a uniform distribution across all deck sizes which would bring its own difficulties (choosing one of an infinite number of configurations uniformly at random leads to all sorts of nastiness).
Joe Fitzsimons
CC BY-SA 2.5
2010-10-10T14:22:58.503Z
@Joe: I think your last comment is about the difficulty of defining a probability distribution of the content of the opponent’s deck.  I agree.  But once a probability distribution is given, I think it is possible to define what it means by “play optimally.”  Of course, the fact that the notion is well-defined does not imply that it is (efficiently or even inefficiently) computable.  But I guess we are going pretty far away from the question, so we should cut off this interesting conversation.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-11T11:28:47.870Z
@Tsuyoshi - I think that would be asking if Magic is decidable. For this question to be meaningful, you could assume perfect information - all libraries and hands are revealed, and all random coin-tosses and the like are predetermined. Is it possible to determine from every Magic position who the winner is?
ripper234
<turing-machines><card-games><recreational>
Is Magic: the Gathering Turing complete?
ripper234
# Is Magic: the Gathering Turing complete?

(Asked by: username_0 on 2010-10-09)

A very specific question, I'm aware, and I doubt it will be answered by anyone that isn't already familiar with the rules of Magic. Cross-posted to [Draw3Cards](http://draw3cards.com/questions/2851/is-magic-turing-complete). Here are the [comprehensive rules for the game Magic: the Gathering](http://www.wizards.com/magic/comprules/MagicCompRules_20101001.txt). See [this question](http://draw3cards.com/questions/2852/an-online-list-of-all-magic-cards) for a list of all Magic Cards. My question is - is the game Turing Complete?

For more details, please see [the post at Draw3Cards](http://draw3cards.com/questions/2851/is-magic-turing-complete).

**Tags:** turing-machines, card-games, recreational

> **Comments:**
> **username_1**: (1) What is the input?  Do you assume that you know the content and the order of the cards in both players’ decks?  (2) To analyze its complexity, a problem must have infinitely many possible inputs.  For example, we cannot say that chess is EXP-complete (even if we say so, it means that the generalization of the chess to an n×n board is EXP-complete).  How do you generalize the game?  (3) The game may be too complicated to analyze its complexity, but I do not know.  
> **username_2**: @Tsuyoshi, RE (2): There is (explicitly) no maximum deck size in M:TG -- that's one of the first things I checked for. [Edit] Also, RE (1): Though you could know the content of players' decks, the order of the cards is explicitly randomized...  
> **username_1**: @Daniel: Thanks.  In fact I checked it too, but I was not sure if anyone wants to analyze the game where each card except for land cards are restricted to at most 4 copies and only the number of land cards can grow.  
> **username_2**: For the game to be Turing-complete, you cannot be able to decide the Halting Problem on it. Even though there are a large number of cards, there are still only finitely many. If you restrict occurrences of each (modulo land cards), it may be possible, at some point, to decide whether you've entered an infinite loop by counting non-land cards.  
> **username_1**: @Daniel: Not sure if the logic works that way because there are several different types of land cards.  After all, the original game itself may be complicated enough to be Turing complete.  What I am not sure is whether the asker really wants to analyze the game where almost all cards in a deck are necessarily land cards.  I will wait for the asker to reply.  
> **username_2**: @Tsuyoshi, you're correct; good catch. As an aside, the asker's link to the other version of the question on Draw3Cards specifies the problem more exactly. I was considering some type of contrived solution involving decks of only land cards (after considering your response) and strategies that would very obviously simulate Turing machine operations, but he wants something that very much looks like an actual game being played.  
> **username_3**: As I see it, there are two possible questions here: 1) Is the game Turing complete when played adversarily (in which case it almost certainly isn't) and 2) is it Turing complete when played collaboratively (in which case it almost certainly is). If case 2 is actually also of interest, then I believe I can post an answer.  
> **username_2**: @Joe, I say post your answer! :)  
> **username_3**: Eek... seems I spoke too soon. The Mana Burn rule keeps breaking my strategy.  
> **username_0**: Wow, I wasn't aware there were so many Magic players here :) Please see the version on Draw3Cards for more clarifications. @Joe - I mean your second question.  
> **username_0**: @Daniel - For simplicity, I allow the decks not to be shuffled before a game starts - although it might be possible to build a deck that has enough tutors and library-arranging effects to work around this limitation.  
> **username_2**: @username_0, I wouldn't say I'm a Magic player -- I played the game as a kid, but I haven't even thought of it for over a decade now (alas, to not grow older!). A quick question while you're here: It seems like Tsuyoshi and I both have inklings of ideas for how to simulate TMs under restrictions that would seem extremely odd to a non-TCS Magic player, but these seem like duds for answering what you're really asking -- could you give some examples of types of restrictions under which you'd still find the problem interesting? [And maybe update the original question with these thoughts]  
> **username_2**: @Joe, does it help if you allow players' lives to be a function of the input size (presumably the deck size)?  
> **username_0**: @Daniel - I don't quite follow. Most restrictions would make solving the problem harder, not easier. Regarding your comment on HP and a finite number of cards, there are infinite combos in Magic, and one can create copies of cards, so in a way Magic has 'infinite scratch-space'. I think that a TM can be simulated even within the restriction of using a finite (small) number of non-land cards which are limited to 4 copies.  
> **username_2**: @username_0, an example of the type of restriction I have in mind is highlighted in Joe's comment earlier: Suppose we restrict the players to playing cooperatively. In this case, you could enforce arbitrary strategies on the players in order to simulate a TM, but it wouldn't look like a game of Magic at all; it would look like a TM represented by Magic cards. Or suppose we further restrict the legal input decks to land cards of only two types (representing 0 and 1) -- then it gets even easier to simulate a TM, but now it DEFINITELY doesn't look like a game of Magic.  
> **username_3**: The original question actually asks for an ordering of the cards too. I can't deal with shuffling yet.  
> **username_4**: @Daniel: That's not a reasonable objection!  Most hardness reductions for games output something that looks more like the reduction than the original game.  (Hamiltonian cycles don't naturally arise in draughts, for example.)  
> **username_4**: @Joe: Why do you think the adversarial game is "almost certainly not" Turing complete?  To simplify the question: Do you think it's decidable whether one player can win in a single turn?  
> **username_3**: Yes. Given that there are a finite number of non-mana cards in even an infinite deck, I think it becomes relatively easy to decide. Further for large shuffled decks the probability of drawing anything other than land is so small the first to draw a useful card will almost surely win.  
> **username_2**: @JeffE, it definitely wasn't an objection! Let's just say "personal caution." :) In light of Joe's beautiful answer (that he posted minutes after that comment of mine), my worries were obviously silly.  
> **username_1**: I read [your other post](http://draw3cards.com/questions/2851/is-magic-turing-complete) (but please include the specification of the question in the question itself, not just a link to it).  I cannot see how the question is related to Turing completeness of a game.  More precisely, I cannot come up with a specific problem L such that this question can be interpreted as asking whether L is Turing complete or not.  
> **username_3**: @Tsuyoshi: I think what the OP was asking for was a specific strategy for the two players, such that deciding who wins when these strategies are used is equivalent to simulating a universal Turing machine, where the input deck encodes the input.  
> **username_1**: @Joe: Thanks for the comment, and I stand corrected: I knew that the question is _related_ to the notion of Turing completeness.  However, I do not think that it is correct to say that the game is Turing complete based on the answer to this question.  
> **username_3**: @Tsuyoshi: Yes, I know what you mean. That is why I phrased my the last sentence of my answer the way I did.  
> **username_0**: @Tsuyoshi, @Joe - this is not what I meant in the question. I meant to ask whether "Magic as a computation device" has power equivalent to a TM. I tried to define what "Magic as a computation device" means on Draw3Cards. If my definition isn't clear and you can help me revise it, that'd be great.  
> **username_1**: The issue is not that your definition is unclear, but that it is different from what is usually referred to as “a game as a computational device.”  Usually, the complexity of a two-player game refers to the complexity of deciding the winner (or finding the best move for the winner) of a given configuration, assuming that both players play optimally.  In this question, the strategies of both players are also given as part of input, and the only restriction is that the Turing machine and its input must be encoded separately.  (more)  
> **username_1**: (cont’d)  This question is about simulating Turing machine by a game in a specific sense, and therefore it is morally related to the notion of Turing completeness.  However, I find the title “Is Magic: the Gathering Turing complete?” rather misleading.  
> **username_3**: @Tsuyoshi: I'm not entirely sure that playing optimally is well defined for Magic. In principle you don't know what cards are in your opponents deck until you see them played. I don't simply mean the ordering, I mean the actual cards. In this case it seems hard to formulate a strategy which is both effective and independent of your opponents deck.  
> **username_1**: @Joe: I agree.  If the content of the opponent’s deck is not known (even as a probability distribution), it is probably impossible to define what it means by “play optimally.”  
> **username_3**: @Tsuyoshi: Yes. Actually, even if the probability distribution were given, it might still be insufficient, as there is no limit on deck size, so you could wind up with something like a uniform distribution across all deck sizes which would bring its own difficulties (choosing one of an infinite number of configurations uniformly at random leads to all sorts of nastiness).  
> **username_1**: @Joe: I think your last comment is about the difficulty of defining a probability distribution of the content of the opponent’s deck.  I agree.  But once a probability distribution is given, I think it is possible to define what it means by “play optimally.”  Of course, the fact that the notion is well-defined does not imply that it is (efficiently or even inefficiently) computable.  But I guess we are going pretty far away from the question, so we should cut off this interesting conversation.  
> **username_0**: @Tsuyoshi - I think that would be asking if Magic is decidable. For this question to be meaningful, you could assume perfect information - all libraries and hands are revealed, and all random coin-tosses and the like are predetermined. Is it possible to determine from every Magic position who the winner is?  

---

## 3 answers

### Answer by username_4 on 2010-11-09. Score: 22 | Accepted answer

[Alex Churchill (@username_7)](https://cstheory.stackexchange.com/users/1713/alexc) has posted a solution that does *not* require cooperation between the players, but rather models the complete execution of a universal Turing machine with two states and 18 tape symbols. For details, see <https://www.toothycat.net/~hologram/Turing/> [[archive](http://archive.is/xbCak)].

> **Comments:**
> **username_6**: The link is dead for me. Should we recreate the solution in the answer to be complete?  
> **username_7**: The solution is being hosted at https://www.toothycat.net/~hologram/Turing/ for the moment.  

---

### Answer by username_3 on 2010-10-09. Score: 15

Ok, I have a solution that avoids the mana burn issue I ran into. This is kind of a hack, since I need to make the assumption that players can identify specific lands, which I don't think is dealt with in the rules. In practice this is the case, since they can be arranged in a line based on the order in which they are played.

First, the full description of the problem from the Draw3Cards site:

> A positive answer would be composed of
> these components:
>
> 1. A computable function fM from Turing Machines to ordered Magic decks
>    (where the order of the library
>    matters)
> 2. Two well defined deterministic & computable strategies to play Magic
>    (that do not depend on the deck).
>    Let's call them Strategy TS (Turing
>    Strategy) and Strategy IS (Input
>    Strategy).
> 3. A computable way fI to encode any string of zeros and ones as a
>    Magic Input deck. One such way would
>    be to take the Gödel number of the
>    string and put as many islands in the
>    Input deck.
>
> The additional condition that should
> be satisfied is this: Given a Turing
> Machines TM, let us consider the
> result of the Magic game between
> strategy TS playing with deck fM(TM)
> against strategy TI playing with deck
> fI(I), when the libraries are not
> shuffled before the game starts. This
> game should be won by the first player
> if and only if TM(I) = true.

So here is the idea. We have 2 players, A and B. B will supply the input, while A will directly implement a Turing machine. The decks will be composed almost entirely of land, but also the [Gemstone Array](http://gatherer.wizards.com/Pages/Card/Details.aspx?multiverseid=50150) card to void mana burn. A will have 3 types of land: Islands, Mountains and Forests. The basic idea is to use tapped land to represent a 1 and untapped land to represent a 0. Islands will be used to represent the state of the tape, Mountains to index the current position along the tape and Forests to represent the internal state of 24 state 2 symbol Turing machine (I believe there is a universal one due to Rogozhin).

The decks are ordered as follows:
A's deck: Gemstone Artifact; 6 Forests (since $2^5 = 32 > 24$ plus an additional forest); For m=0 to infinity: $2^{m+1}$ Islands followed by 1 Mountains. Note that the number of mountains (which can be either tapped or untapped) is always the number required to index every island, plus a halting state.

B's deck: Gemstone Artifact; 6 Forests (since $2^5 = 32 > 24$ plus an additional forest); For m=0 to infinity: $2^{m+1}$ Input Lands followed by 1 Mountains. Note again that the number of mountains (which can be either tapped or untapped) is always the number required to index every island held by A, plus a halting state. The Input lands are taken to be Plains (to represent a 0 in the input string), Swamp (to represent a 1 in the input string) and Islands (which are used after the end of the input string has been reached.

Strategy:
A and B both play one land a turn in the order in which they are drawn.
When each has drawn 4 forests they play Gemstone Artifact.
Note A goes first, so already has an Island when B draws plays his first input card.

A and B simply continue to place their cards in order until B has exhausted their Plains and Swamps and plays their first Island. On his next go, A for all i taps his ith Island iff Bs ith Input Land was a swamp. A initialises his turing machine by tapping his first Forest and Mountain. If he has tapped an odd number of cards he taps his extra forrest, and uses all this mana to add tokens to Gemstone Array. From here on the play proceeds as follows: B uses their turn to simply mirror the state of A's mana. B taps his ith Input Land iff A's ith Island is tapped. Similarly B taps his ith Forest(Mountain) iff A's ith Forest(Mountain) is tapped. As A always taps an even number of cards, so does B, and the mana is used to add tokens to Gemstone Array.

On A's turn, all of A's mana becomes untapped, so A looks at the state of B's mana, represents the state of A's mana on the previous turn. A applies the transition rule according to the universal (24,2) machine to B's state to obtain his new state.

Play proceeds in this manner until the turing machine halts. At this point, A puts his mountains into the reserved "finished" state (the all untapped state). If the Turing machine halted in an accepting state, B copies the state of A's mountains, but taps all their remaining land neglecting to use Gemstone array, thus beginning the process of suicide by mana burn. On A's turn, if B's mountains are in the "finished" state, and all B's other land is tapped, A simply does nothing (note that his mountains are automatically in the "finished" state). If A's mountains are in the finished state, but nothing else is tapped, B continues suicide by mana burn. This is repeated until B is dead.

If however, the machine finishes in the reject state, B leaves all their cards untapped. If all B's cards are untapped, A taps all his cards, beginning the same process of suicide by mana burn. If A's non-Mountain cards are all tapped, and the mountains untapped, B leaves all their cards untapped. This will lead A to continue the mana burn suicide until he loses the game.

This should satisfy the criteria asked for in the question, and hence when this ordering is allowed, I believe the game is Turing complete in the sense described in the question.

> **Comments:**
> **username_2**: Cool. An extra thought: As long as any player taps more than 1 land per turn, you can use charges on the Gemstone Array to avoid mana burn. For example, if I need to tap 3 lands, I turn two mana into a charge, spend the charge to generate one mana, then spend the two remaining mana to create a new charge. -- of course, you solved this problem already anyway. :)  
> **username_3**: Actually, it just occurred to me that you could use a universal cellular automata instead with the same techniques, but that this would cut down on the number of different types of land required.  
> **username_4**: Aewsome!  It might also be easier to simulate a 2-counter machine (using different types of mana as the counters) instead of directly simulating a Turing machine: http://en.wikipedia.org/wiki/Counter_machine#Two-counter_machines_are_Turing_equivalent_.28with_a_caveat.29  
> **username_4**: Your reduction also implies that (cooperative) Magic with a finite number of cards is PSPACE-hard.  
> **username_3**: Does that follow? I believe the game ends if either player runs out of cards. There may be a card which can be used to circumvent this by recycling graveyard cards.  
> **username_0**: @Joe - there is no longer mana burn in Magic. You could use Platinum Angel to avoid losing due to running out of cards in your graveyard.  
> **username_3**: Well mana burn can easily be removed by adding a creature to each deck as the second card to be held until the TM halts, at which point if it is in an accepting state A summons the creature, otherwise B does. Whoever has a creature in play simply repeatedly attacks until their opponent is dead.  
> **username_2**: @Joe, another minor aside: If a player ever recognizes a accepting/rejecting state on the board, it is a legal move in Magic to simply concede on the spot (or do nothing and let the opponent concede). In fact, the language in the official rules seems to suggest that the "right to concede, anytime" is the sole inalienable right in any Magic game. (Although, maybe this isn't as elegant as causing an actual winning/losing condition to occur in-game.)  
> **username_0**: I am still missing one thing - you have not provided a way, given a finite deck for player A, to do calculations that require arbitrary size. The amount of lands you have can have in play is finite, so there must be a flaw in your proof sketch.  
> **username_0**: However, that should be easy to circumvent: http://draw3cards.com/questions/2860/how-do-you-create-an-arbitrary-number-of-lands-that-last-for-the-next-turn  
> **username_0**: @Joe - you missed my comment earlier that the concept of mana burn has been completely removed from the rules. You can fix it by having each player have a copy of Fireball in his deck.  
> **username_3**: @username_0: I didn't miss it. See my comment above about including a creature to deal damage. Also, I am not sure what you mean about the land being finite. At any step i there will be i land in play, but since I don't know when the Turing machine halts, I need an infinite deck.  
> **username_3**: @username_0: I assume the platinum angel rule only applies when it is alive? Otherwise the computation never halts. But in that case, I believe the addition of it would indeed allow for JeffE's corollary, provided you also include a way to kill it.  
> **username_0**: @Joe - You can't have an infinite deck for player A. His deck is fixed as the "algorithm" deck. Player B's deck can also not be infinite - his deck represents some finite input. You can create an infinite (well, arbitrarily high) number of land tokens if you need. Yes, Platinum Angel only works when it's alive.  
> **username_0**: Also, see @Alextfish's solution on Draw3Carsd: http://draw3cards.com/questions/2851/is-magic-turing-complete/2866#2866  

---

### Answer by username_5 on 2019-06-17. Score: 10

Alex Churchill, Stella Biderman and Austin Herrick published [this paper](https://arxiv.org/abs/1904.09828) showing that Magic is Turing Complete

> 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, solving a problem that has been open for a decade [1], [10]. 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 recognising who will win a game in which neither 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 unified computational theory of games and remarks about the playability of such a board in a tournament setting.


---

