{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:44Z","timestamp":1753893824384,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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.\u00a0Two 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.<\/jats:p>","DOI":"10.37236\/2244","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T01:22:15Z","timestamp":1578705735000},"source":"Crossref","is-referenced-by-count":9,"title":["From Heaps of Matches to the Limits of Computability"],"prefix":"10.37236","volume":"20","author":[{"given":"Urban","family":"Larsson","sequence":"first","affiliation":[]},{"given":"Johan","family":"W\u00e4stlund","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2013,9,20]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v20i3p41\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v20i3p41\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T11:13:33Z","timestamp":1579259613000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v20i3p41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,20]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2013,7,19]]}},"URL":"https:\/\/doi.org\/10.37236\/2244","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2013,9,20]]},"article-number":"P41"}}