AlexTFish

To me it looks like the emergency vehicles are counted as violating the rules by about 60% of players? Which I assume is meant in the sense of "yes, this technically breaks the rules, but we assume they had good reason to (because they were following higher-scope rules)".

FWIW that's my old site, showing the 2012 version of the result, which required cooperation between 4 players. The version in the paper on arXiv is the result of my latest research (with Stella and Austin) where we get it down to 2 players and eliminate all choices required by any player.

I am planning to update the toothycat.net site pretty soon with this new result, though.

As the other repliers have explained, MtG provides various ways to circumvent that. Thus we found ways to encode millions of pieces of state in tokens, and we ensured that the game loops round computing the Turing machine execution one step at a time.

Your sentence "There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large" is actually key. You're completely right - there are many. What's unusual about our result here is that we found a way to embed a fully functional Turing machine inside not an arbitrary extension of a board game, but inside a board game exactly the way it's normally played.

The Shahrazad deck also presumably needs either Plains or Black Lotus.

This isn't an error. The machine doesn't use phasing to trigger enter-the-battlefield triggers, merely to switch between the two states (sets of Rotlung Reanimators watching for the current token dying).

The machine as demonstrated on that page requires 4 players. There are probably ways to do it with fewer, but you might have to accept situations where two abilities trigger and the players need to choose an order to put them on the stack (though it makes no difference either way).

On the "Cards" page, http://www.toothycat.net/~hologram/Turing/Cards.html:

> The first sixteen Reanimators were cast in the normal fashion, four by each of the players, and donated by a Bazaar Trader. The other twenty are Clones and Vesuvan Shapeshifters copying a Rotlung Reanimator. The phasing enchantments can include Teferi's Curse, Cloak of Invisibility, and Copy Enchantment, cast by any player and donated by a Bazaar Trader. These creatures and Auras must not be tokens, because tokens disappear when phased out.