transparent gif

 

Ej inloggad.

Göteborgs universitets publikationer

From heaps of matches to the limits of computability

Författare och institution:
Urban Larsson (Institutionen för matematiska vetenskaper, matematik, Chalmers/GU); Johan Wästlund (Institutionen för matematiska vetenskaper, matematik, Chalmers/GU)
Publicerad i:
Electronic Journal of Combinatorics, 20 ( 3 ) s. Paper 41
ISSN:
1077-8926
Publikationstyp:
Artikel, refereegranskad vetenskaplig
Publiceringsår:
2013
Språk:
engelska
Fulltextlänk:
Fulltextlänk (lokalt arkiv):
Sammanfattning (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 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.
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
NATURVETENSKAP ->
Matematik ->
Diskret matematik
Nyckelord:
Combinatorial Games, Computational Complexity, Logic in Computer Science, SUBTRACTION GAMES, P-POSITIONS, INVARIANT
Ytterligare information:
Preprint on arXiv: http://arxiv.org/abs/1202.0664
Postens nummer:
185380
Posten skapad:
2013-10-18 13:16
Posten ändrad:
2016-07-05 10:50

Visa i Endnote-format

Göteborgs universitet • Tel. 031-786 0000
© Göteborgs universitet 2007