Добавить новость
ru24.net
News in English
Июнь
2019

You can make a Turing machine inside a game of Magic: The Gathering

0

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




Moscow.media
Частные объявления сегодня





Rss.plus




Спорт в России и мире

Новости спорта


Новости тенниса
Марат Сафин

Марат Сафин сделал прогноз на финал Australian Open Янник Синнер — Александр Зверев






В Госдуме в приоритетном порядке рассмотрят проект об ОГЭ по двум предметам

Онугха вернулся в «Вайле» через пять месяцев после перехода в «Копенгаген»

«Сьон» с Миранчуком разгромно проиграл «Базелю» в чемпионате Швейцарии

Вид с воздуха на Черкизовский рынок, 8 июня 2008 года, Москва