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
Escape from the Haunted Mansion is a massive, ambitious free papercraft project to download, print, mount on coreboard, cut out, assemble and play. I have no idea if the gameplay is any good, but the model is freaking gorgeous. It's from the good folks at Disney Experience, who have a wealth of papercraft Disney projects […]
The Switch Lite doesn’t connect to a TV set, but it’s otherwise a slim, pocketable version of Nintendo’s popular portable game console. The Switch Lite — the newly unveiled spinoff of the full-sized Switch console — doesn’t actually “switch.” Instead of the detachable controllers and TV dock that allows the standard Switch to shape-shift between […]
The Procgen Mansion Generator produces large three-dee dwellings to toy with your imagination, offering various architectural styles and other options. Each mansion even comes with floorplans:
If you suffer from sleep disorders, there are a number of methods out there to mitigate them: Ambient noisemakers, relaxation tapes, sleep masks, you name it. One thing that doesn’t get tried is headphones, for good reason. Even the smallest earbuds are liable to wake you up if you roll over the wrong way. Now […]
Looking to upgrade that old laptop or tablet? Holiday sales may be way on the horizon, but there’s an even better way to get like-new tech for a steal. Here are 10 of our favorite deals on personal computers and gaming gear – refurbished, renewed or brand new. Acer Touchscreen 11′ Chromebook 16GB (Certified Refurbished) […]
Vape technology has been around long enough that vapers are starting to get picky about their gear. Luckily, so are we. From disposable models to cutting-edge touchscreen atomizers, there’s a vaporizer in this roundup to suit every taste. Hera 2 – World’s Most Advanced Dual-Use Vaporizer Choose between dry herb or oil extraction modes – […]