From heaps of matches to the limits of computability (Q396877)

Summary: We study so-called invariant games played with a fixed number \(d\) of heaps of matches. A game is described by a finite list \(\mathcal{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 \(\mathcal{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) \in \mathcal{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 \(\mathcal{M}\) and \(\mathcal{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.