From Heaps of Matches to the Limits of Computability
Open Access
- 19 July 2013
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 20 (3) , P41
Abstract
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.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- COFINITE INDUCED SUBGRAPHS OF IMPARTIAL COMBINATORIAL GAMES: AN ANALYSIS OF CIS-NIM2014
- Impartial games emulating one-dimensional cellular automata and undecidabilityJournal of Combinatorial Theory, Series A, 2013
- The-operator and invariant subtraction gamesTheoretical Computer Science, 2012
- Lattice games without rational strategiesJournal of Combinatorial Theory, Series A, 2012
- Combinatorial games with a pass: A dynamical systems approachChaos: An Interdisciplinary Journal of Nonlinear Science, 2011
- Invariant gamesTheoretical Computer Science, 2010
- Extensions and restrictions of Wythoff's game preserving its positionsJournal of Combinatorial Theory, Series A, 2010
- Playing games with algorithms: Algorithmic combinatorial game theory2009
- How Far Can Nim in Disguise Be Stretched?Journal of Combinatorial Theory, Series A, 1998
- A mathematical investigation of games of “take-away”Journal of Combinatorial Theory, 1966