Within normal rules of collectible card game Magic: The Gathering a player may find themselves constrained to only a single legal course of action forward. It’s a situation players could craft to frustrate their opponents, though the victims usually break free after a few moves. But under a carefully crafted scenario, players would have no choice but to become the execution engine for a Turing-complete programming language written with Magic cards via techniques detailed in this paper.
One of the authors of this paper, [Alex Churchill], started working on this challenge in 2010. We covered an earlier iteration of his work here, and his own criticism that it was dependent on player cooperation. At various points, the game rules state a player “may” take certain actions and the construct falls apart if our player chooses the wrong thing. It would be as if a computer was built out of transistors that “may” switch as commanded or not, which would not be a very reliable method of computation.
To improve reliability of this particular Turing machine execution engine, the team combed through rules and cards to devise an encoding where the player is only ever presented with a single legal course forward. This ensures deterministic execution of the instruction stream, and now with proof of Turing-completeness in hand, we congratulate [Alex] on a successful conclusion to his decade-long quest.
We have a primer available for anyone who wants a refresher on Turing machines. They are utterly impractical but fun for hackers to build, and they are typically constructed of electronics and LEDs instead of ink on cardboard.
Via Ars Technica, who have presented their own analysis of this machine.
Main image: Unspecified set of Magic: The Gathering cards by [Robert] CC BY 2.0
A (Card) Table-Top Turing Machine Of Magic: The Gathering Cards
Source: HackADay
