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. Here are the comprehensive rules for the game Magic: the Gathering. See this question for a list of all Magic Cards. My question is - is the game Turing Complete?
For more details, please see the post at Draw3Cards.
Alex Churchill (@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].
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:
- A computable function fM from Turing Machines to ordered Magic decks (where the order of the library matters)
- 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).
- 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 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.
Alex Churchill, Stella Biderman and Austin Herrick published this paper 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.
