Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
June 24, 2019 06:16 pm PDT

You can make a Turing machine inside a game of Magic: The Gathering

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 strategyequivalent 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

"Its possible to build a Turing machine within Magic: The Gathering" (Ars Technica)

Read the rest


Original Link: http://feeds.boingboing.net/~r/boingboing/iBag/~3/Df83pwiG5JI/you-can-make-a-turing-machine.html

Share this article:    Share on Facebook
View Full Article