You can make a Turing machine inside a game of Magic: The Gathering
lundi 24 juin 2019, 20:16 , par BoingBoing
Magic: The Gathering is Turing complete. In a new scientific paper, researchers 'present a methodology for embedding an arbitrary Turing machine into a game of Magic such that the first player is guaranteed to win the game if and only if the Turing machine halts.' From Ars Technica:
Furthermore, (software engineer Alex Churchill) and his co-authors -- Stella Biderman of the Georgia Institute of Technology and Austin Herrick of the University of Pennsylvania -- have concluded that Magic might be as computationally complex as it's possible for any tabletop game to be. In other words, 'This is the first result showing that there exists a real-world game [of Magic] for which determining the winning strategy is non-computable,' the authors write...
A universal Turing machine is one capable of running any algorithm, while 'Turing completeness' is a term 'used to indicate that a system has a particular degree of complexity,' said Churchill. 'Any Turing-complete system is theoretically able to emulate any other.' Being able to determine whether a given problem can be solved in principle is a key task in computer science. If Magic is Turing complete, then there should exist within the game a scenario where it's impossible to determine a winning strategy—equivalent to the famous 'halting problem' in computer science.
One way to demonstrate that a system is Turing complete is to create a Turing machine within it, and that's just what Churchill et al. have done with their work
'It’s possible to build a Turing machine within Magic: The Gathering' (Ars Technica)
56 sources (32 en français)
mar. 20 oct. - 04:55 CEST