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
Cities: Skylines too.
https://medium.com/@balidani/cities-skylines-is-turing-complete-e5ccf75d1c3a
I wonder if its possible to build actual logic gates and such in Super Mario Maker (and whether that could be considered turing complete). The on-off switches in the new game might help with that.
Definitely. Turtles are the key. It would be slow given the time it takes them to pop back out but that’s one thing that sticks out to me as having controllable states to represent on-off.
Yes, someone already made an addition calculator with carry overflow, including 7-segment displays for output
https://kotaku.com/someone-created-a-working-calculator-using-mario-maker-1757806214
There’s a meme waiting to break out. Gamers have Doom on everything. Geeks see logic gates everywhere.
If you have logic gates, you can run Doom on it…
The difference between this setup and Minecraft-like constructions (simulations/sandboxes) is that this one involves the strategic play of the game: which means if you were a computer trying to figure out how to win Magic and got faced with this situation, you would have to solve the halting problem. Which means unlike almost any other game, you can’t “solve” Magic.
Which doesn’t surprise me, given the number of cards which can rewrite the rules of the game.
I made a video that describes how it is possible to compile any program into a Magic Turing Machine. Spoiler: Don’t try to build one with cards. https://www.youtube.com/watch?v=YzXoFldEux4