Re:Accidentally Turing-Complete
by FartyMcFarter on Friday April 24, 2020 @06:24AM
(#22966491)
On Magic The Gathering being Turing-complete, this is an interesting quote:
> Our result is also highly unusual in that all moves of both players are forced in the construction. This shows 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.
At first I thought this was pretty mind-blowing for a game, but actually this is directly comparable with a Turing machine; each step is forced, mechanical and very easy to derive, and yet, the overall behaviour is generally undecidable.
Re:Accidentally Turing-Complete
by lukifer on Friday April 24, 2020 @01:06PM
(#22970390)
For anyone curious about the details of building a Turing machine in MtG, Because Science did a thorough breakdown and demonstration, using actual cards: https://youtu.be/pdmODVYPDLA
> Our result is also highly unusual in that all moves of both players are forced in the construction. This shows 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.
At first I thought this was pretty mind-blowing for a game, but actually this is directly comparable with a Turing machine; each step is forced, mechanical and very easy to derive, and yet, the overall behaviour is generally undecidable.