CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

From heaps of matches to the limits of computability

Urban Larsson (Institutionen för matematiska vetenskaper, matematik) ; Johan Wästlund (Institutionen för matematiska vetenskaper, matematik)
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


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)


Diskret matematik

Chalmers infrastruktur