# From heaps of matches to the limits of computability

**Electronic Journal of Combinatorics**(1077-8926). Vol. 20 (2013), 3, p. Paper 41.

[Artikel, refereegranskad vetenskaplig]

We study so-called invariant games played with a fixed number d of heaps of matches. A game is described by a finite list M of integer vectors of length d specifying the legal moves. A move consists in changing the current game-state by adding one of the vectors in M, provided all elements of the resulting vector are nonnegative. For instance, in a two-heap game, the vector (1, -2) would mean adding one match to the first heap and removing two matches from the second heap. If (1, -2) is an element of M, such a move would be permitted provided there are at least two matches in the second heap. Two players take turns, and a player unable to make a move loses. We show that these games embrace computational universality, and that therefore a number of basic questions about them are algorithmically undecidable. In particular, we prove that there is no algorithm that takes two games M and M' (with the same number of heaps) as input, and determines whether or not they are equivalent in the sense that every starting-position which is a first player win in one of the games is a first player win in the other.

**Nyckelord: **Combinatorial Games, Computational Complexity, Logic in Computer Science, SUBTRACTION GAMES, P-POSITIONS, INVARIANT

*Preprint on arXiv: http://arxiv.org/abs/1202.0664*

Denna post skapades 2013-10-18. Senast ändrad 2016-07-05.

CPL Pubid: 185380