Navigation
Recherche

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 coauthors  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 realworld game [of Magic] for which determining the winning strategy is noncomputable,' 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 Turingcomplete 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)
https://boingboing.net/2019/06/24/youcanmakeaturingmachine.html

56 sources (32 en français)
Date Actuelle
mar. 20 oct.  04:55 CEST
