Search: onr:"swepub:oai:gup.ub.gu.se/185380" >
From heaps of match...
From heaps of matches to the limits of computability
-
- Larsson, Urban, 1965 (author)
- Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper, matematik,Department of Mathematical Sciences, Mathematics,Chalmers tekniska högskola,Chalmers University of Technology,University of Gothenburg
-
- Wästlund, Johan, 1971 (author)
- Gothenburg University,Göteborgs universitet,Institutionen för matematiska vetenskaper, matematik,Department of Mathematical Sciences, Mathematics,University of Gothenburg,Chalmers tekniska högskola,Chalmers University of Technology
-
(creator_code:org_t)
- The Electronic Journal of Combinatorics, 2013
- 2013
- English.
-
In: Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1077-8926 .- 1097-1440. ; 20:3
- Related links:
-
https://gup.ub.gu.se... (primary) (free)
-
show more...
-
http://publications.... (primary) (free)
-
https://www.combinat...
-
https://gup.ub.gu.se... (primary) (free)
-
https://gup.ub.gu.se...
-
https://research.cha...
-
https://research.cha...
-
https://doi.org/10.3...
-
https://gup.ub.gu.se...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Keyword
- Combinatorial Games
- Computational Complexity
- Logic in Computer Science
- SUBTRACTION GAMES
- P-POSITIONS
- INVARIANT
- Combinatorial Games
- Algorithmically undecidable
- Cellular Automata
- Game complexity
- Heap game
- Impartial game
- P-equivalence
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database