The authors (Churchill et al) make a rather strong claim:
Prior to this work, no undecidable real games were known to exist.
By "real game" they seem to mean a game played with the rules that are used in real life, rather than modifications of the rules. This may be where reporters got the idea that Magic is "the most complicated game", so it's worth examining.
The rules of most games immediately rule out Turing completeness, as the authors themselves point out:
As most games have finite limits on their complexity (such as the size of a game board) most research in algorithmic game theory of real-world games has primarily looked at generalisations of commonly played games rather than the real-world versions of the games.
(I added the Wikipedia link.)
Turing completeness requires an unbounded number of states and an unbounded number of moves (reference: any computer science text), so the claim that Magic as actually played is Turing complete includes the claim that there is no limit on the duration, move count, or size (number of pieces in play) of a game in the real-life rules. For example, if you are only allowed to use cards and tokens that were manufactured before the game started, then the number of pieces in play is bounded, and the game is (in the authors' words) "trivially decidable" as a result. I don't know whether rules of that sort exist in Magic tournaments, but I would expect that they do, either explicitly or as a consequence of other explicit rules.
In the abstract they also claim
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.
Undecidability requires an infinite set of problem instances, so this claim doesn't apply to initial states (decks), since those are always limited in size and content by the rules. It applies to games which started an unbounded number of moves ago, in which the players have already made an unbounded number of non-trivial decisions, since that's the only way to created an unbounded number of different states. (It also applies only if the rules satisfy the requirements of Turing completeness as mentioned above.)
They also make the following odd claim:
[L]eading formal theory of strategic games claims that the unbounded memory required to simulate a Turing machine entirely in a game would be a violation of the very nature of a game [9].
They return to this later, and seem to believe that they've shown that existing models of games are inadequate to describe Magic, which is definitely wrong. Reference [9] is "Constraint Logic: A Uniform Framework for Modeling Computation as Games" by Demaine and Hearn. Churchill et al may be referring to the section "What is a game?" where Demaine and Hearn say
One key difference [between games and Turing machines] is in the size of the state: Turing machines have infinite tapes, so the state at any time is unbounded, while we always require the state of a game to be defined by a finite board position. We can, of course, bound the size of a Turing-machine tape, or use a circuit model of computation, but such restrictions limit the model of computation from general decidability. By contrast, we show that no such limitations exist for games.
It's unclear to me what Demaine and Hearn are trying to say here. The statement that "the state at any time is unbounded" is false at face value. The state of a Turing machine at any time is finite (i.e., finitely describable) in the same way as the games they model. Since they say "no such limitations exist for games", and later use Conway's Life (which has long been known to be Turing complete) as an example of a game, it seems clear that their framework does support games like unbounded Magic – and even if it doesn't, there is nothing remotely new about the idea of mathematically modeling such games.
Churchill et al in their conclusion even say
it seems likely that a super-Turing model of games would be necessary to explain Magic.
(italics theirs). If this is a claim that Magic might violate the Church-Turing_thesis – and I see no other way to interpret it – then it's absurd, and completely unsupported by the rest of the preprint.
The answer so far is based on the arXiv preprint. This work has also been published as a peer reviewed conference paper, according to Biderman's CV. The full conference proceedings including this paper are available here. The published version seems to be essentially the same, including even the more extreme claims from the preprint, which leads me to question the competence of the reviewers and editors.
