** Magic: The Gathering is non-computable complex game.**

Researchers have shown that the table-top card game Magic: The Gathering is the most difficult game of all analyzed games that people play.

It turned out that the existence of an algorithm that computes, win the player that is equivalent to the halting problem is a classical problem of the theory of algorithms, undecidability which was proved by Alan Turing in 1936. Thus, Magic: The Gathering is non-computable complex game, the authors write in the paper on the website arXiv.org.

In theoretical computer science to formalize the notion of algorithm uses the Turing machine is an abstract computer, which consists of an infinite tape divided into discrete cells, and a control device that can be read from the tape information and record it. The device can be in a specific finite number of internal States, varying which it is possible to implement different algorithms.

Using this theoretical model Alan Turing in 1936 proved the unsolvability of the problem stop, that is, the impossibility of the existence of an algorithm that could predict in advance, whether to stop this Turing machine in the computation of this input information, or will indefinitely conduct operations, never coming to final answer. In other words, the algorithm of the Turing machine deciding the halting problem is non-computable.

The majority of real problems are computable and they are usually classified according to the degree of intensity. The most simple are solvable in polynomial time tasks, which together form a set P. For them, the number of steps the Turing machine to obtain the answer grows faster than nk, where k is a constant, and n is the number of occupied input data cells on the tape. An example of such a simple task is to compute whether two natural numbers are coprime, in other words, if they have a common divisor besides unity.

Examples of the category of much more complex tasks is EXP, which includes problems that can be solved in exponential time, that is, the number of operations required grows faster than kn, and a function for sufficiently large n will grow much faster than nk, regardless of k. There are many intermediate classes of complex algorithms, which may differ not only takes time but also space, that is, the number used for the calculations of cells. There are also tasks for which the algorithm does not exist, such as the halting problem.

In addition to the abstract mathematical computations in classes of difficulty to rank various games like chess, which fall in EXP. The vast majority of the studied by mathematicians for real games has the top rating of difficulty and not up to non-computable task, so most of the research on algorithmic game theory first considered a generalization of the standard games, not existing in reality options. From real games proved that non-trivial complexity have a “Point” (“dots and squares”, “sticks”), “jenga” and “Tetris”.

The work of the independent researcher Alex Churchill (Churchill Alex) from the UK, as well as mathematicians Stella Biderman (Biderman Stella) from Georgia Institute of Technology and Austin Herrick (Herrick Austin) at the University of Pennsylvania, presents a mathematical formalization of the game Magic: The Gathering. For this the authors are with the existing cards and rules for two players implemented a universal Turing machine, and the winner in this case is equivalent to the halting problem for this machine. On the one hand, for the first time (in the words of the authors) shows an example of a real game, in which the definition of non-computable winning strategies, and with another – proves the impossibility in the General case of testing equivalence of different strategies in this game.

In addition to interest in the context of the game, a new result can also have a significant influence on the foundations of game theory, as today, the prevailing view suggested that the outcome of any game should be theoretically computable. According to these authors, Magic: The Gathering is not consistent with the hypotheses usually employed in the simulation games on computers.

© 2019, https:. All rights reserved.