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 article by Holly Gramazio suggests several ideas for games you can play alone or with friends while in public. My favorite of the lot was posted by a Redditor, and seems like a great way to feel more positive about the world: When I’m out in public or driving or something, I like to […]
Paolo Pedercini compares every bee-themed game with an eye to their scientific accuracy. Bees, particularly honeybees, are often incorrectly characterized in videogames – as well as in other media. Sometimes that’s due to their similarity with with the more aggressive wasps (which make for better enemies), sometimes that is due to the alien-like complexity of […]
Enjoy this compilation of 1990s-era sprite games extruded into lowpoly 2½D extravaganzas. These are works of static art, but I’m sure I’ve seen this done “live” in-game recently, in an automated, playable way. (Note that there are a number of 2½D Super Marios already–these replicas are hand-made, like this video).
We love our smartphones and tablets, but we also love to write. For a while now, there hasn’t been a workable solution. Either hook it up to a keyboard (which defeats the purpose of a portable gadget) or resign ourselves to typing on tiny, unresponsive glass icons. Looks like technology has finally caught up to […]
So you’ve got an iPhone 11 Pro Max. It’s an impressive piece of hardware – sometimes, too impressive. The more you’re compelled to use it, the more an age-old problem pops up: The dreaded low battery warning. Even if you’re on the go, perhaps the best solution to this is also pretty unobtrusive. It’s the […]
The good news: Software like Adobe Premiere Pro, Camtasia and Final Cut Pro has opened up a ton of possibilities for desktop videographers. On the other hand, their use is so widespread that you have to be an expert in them before you can even think about a career in the field. That’s a requirement […]