Magic: The Gathering Is Turing Complete

A note on this submission: This paper differs from previous "Magic is Turing-complete" links you may have seen here in that this construction embeds a universal Turing machine that runs without requiring the players to make particular choices.

Note that the previous "Magic is Turing-complete" links you may have seen here were presumably pointing to the earlier constructions by Alex Churchill, which, as mentioned, required the players to make particular choices. Well, in this paper, Churchill (along with Biderman and Herrick) have finally gotten rid of the holes in the construction; once the machine starts running, the players have no more choices at all and cannot stop its operation.

So, now Magic is actually proven to be Turing-complete, unlike Churchill's earlier constructions, which just showed it to be, uh, sort-of Turing-complete.

FWIW, the key innovation in this paper (compared to the earlier constructions) is the use of Wild Evocation, together with Wheel of Sun and Moon, to force Alice (player 1) to cast her cards in a specified sequence for the rest of the game. (Well, one of two specified sequences, as Coalition Victory is sometimes skipped due to Mesmeric Orb and Xathrid Necromancer, but that's details.)