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
Analogue Pocket is a forthcoming handheld game console that runs old Nintendo carts and offers a built-in synthesizer and sequencer. A multi-video-game-system portable handheld. A digital audio workstation with a built-in synthesizer and sequencer. A tribute to portable gaming. Out of the box, Pocket is compatible with the 2,780+ Game Boy, Game Boy Color & […]
Blizzard's cowardly decision to appease Chinese authoritarians by ejecting a champion player who expressed support for the pro-democracy struggle in Hong Kong has kicked off a global rebellion by the company's customers, who are furious that the firm has put its profits over an entire nation's right to self-determination and basic democratic freedoms.
After a day of making people look at a black hole, Epic Games has released the next iteration in the amazingly popular battle royale shooter Fortnite. A new map, boats and bandage bazookas are just some of the ‘new’ things. Players can now carry an injured buddy to safety, or go fishing — maybe both […]
Treat yourself, internet: We’ve rounded up some deals from the past week that were too good not to bring back for an encore. Take your pick from home goods, massagers and other tech, all at serious discounts. TREBLAB Z2 Bluetooth 5.0 Noise-Cancelling Headphones Get in the groove and stay that way with these headphones and […]
As cool as your smartphone is, it can’t do everything. When a job requires a little elbow grease, a multitool is a great thing to have around – and might just save your life in the right situation. Here’s a roundup of some of the latest multitool designs, which have come a long way since […]
Whether you own or rent your place, insurance on that home is a necessary hassle – but a new tech-driven company called Lemonade is starting to show that while it might indeed be a necessity, it doesn’t have to be a hassle. Here’s the way insurance typically works: You pay premiums and hope an accident […]