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
This is a really cool homebuilt arcade game project.
What you see before you here is frenetic, graphics-heavy 1985 arcade game Space Harrier as a textmode app. Though represented as chunky extended-ASCII characters, the underlying game is startlingly authentic, with bosses, pylons, tunnel staages and music all running at the Sega classic’s freakishly fast clip. It’s not a clever terminal project floating up on […]
In the 1990s, Nintendo and Sony collaborated on a new game console. Nintendo quit the deal suddenly, one of the greatest business mistakes in video game history. Sony developed and released its own version of the PlayStation console, to spectacular success. But there was a prototype “Nintendo PlayStation”, and the working device is up for […]
Spring cleaning time is right around the corner, and, if we’re being honest, the whole thing is kind of a drag. But keeping your home clean in any season is necessary for both health and happiness, so why not make it a little less daunting? The correct tools help make any work easier, and that’s […]
Quality knives matter — and in more ways than you might expect. At the most basic level, having a functioning set of proper kitchen knives means you can actually get in a kitchen, start putting together a meal and have the right tools to handle all tasks. From the blunt force of the clever to […]
You kill it at the gym all week, your nutrition is dialed in, and you’re drinking so much water that your spare time is spent walking back and forth to the bathroom (way to get those steps in!)—so how do you take things to the next level? By focusing on recovery. A proper post-workout routine, […]