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)
image: "Magic: The Gathering collector cards" by Michael Coghlan
I have been loving Shieldwall, a strategy game where you and your Roman legion attempt to kick the crap out of other Roman legions! This game reminds me of a 3D Starcraft, with (thus far) a lot less complexity. You start with one base and attempt to take others from other CG teams! More bases […]
This cat sure appears to be having a fun time.
Matt Ruff is one of science fiction and fantasy's most consistently brilliant and innovative authors, whose recent work includes The Mirage (an incredible alternate history in which the Global War on Terror is kicked off when Christian crusaders from the blighted, tribal USA fly a plane into the United States of Arabia's Twin Towers in Dubai, giving the hawkish CIA chief Osama bin Laden the chance to launch the all-out war he's been champing for), and Lovecraft Country (an anti-racist reimagining of Cthulhu set in Jim Crow America where the real horror is white supremacy -- now being adapted for TV by Jordan Peele). In his new novel, 88 Names, Ruff adds to the canon of MMORPG heist novels (Charlie Stross's Rule 34, Neal Stephenson's Reamde, and my For the Win, to name three) with a unique take that he dubbed "Snow Crash meets The King and I."
Companies that don’t have their own in-house design teams (which means 99 percent of all companies these days) face lots of serious questions. Among those questions is how you keep up with all the design requirements of a 21st-century company without the personnel. It isn’t just a website or an annual product catalog anymore. It’s […]
In case you’re one of those computer shoppers who instinctively turns up their nose at the very mention of the word refurbished, here are a couple myths worth dispelling. Refurbished equals junk somebody didn’t want. While desktops, laptops, notebooks, Chromebooks and tablets marked as refurbished may have been unboxed at some point, meaning they can […]
Electric bikes aren’t toys. And they aren’t a fad. In fact, more and more communities are starting to catch on that e-bikes are a lot more than an amusing gadget for the tech geek. Following a six-month study, Johnson County, Kansas, home to many Kansas City suburbs, became just the latest U.S. community to allow […]