### Skapa referens, olika format (klipp och klistra)

**Harvard**

Larsson, U. och Wästlund, J. (2013) *From heaps of matches to the limits of computability*.

** BibTeX **

@unpublished{

Larsson2013,

author={Larsson, Urban and Wästlund, Johan},

title={From heaps of matches to the limits of computability},

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.
},

year={2013},

keywords={Algorithmically undecidable, Cellular Automata, Game complexity, Heap game, Impartial game, P-equivalence },

note={15},

}

** RefWorks **

RT Unpublished Material

SR Electronic

ID 175717

A1 Larsson, Urban

A1 Wästlund, Johan

T1 From heaps of matches to the limits of computability

YR 2013

AB 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.

LA eng

LK http://publications.lib.chalmers.se/records/fulltext/175717/local_175717.pdf

OL 30