Sökning: onr:"swepub:oai:gup.ub.gu.se/185380" >
From heaps of match...
From heaps of matches to the limits of computability
-
- Larsson, Urban, 1965 (författare)
- 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 (författare)
- 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
- Engelska.
-
Ingår i: Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1077-8926 .- 1097-1440. ; 20:3
- Relaterad länk:
-
https://gup.ub.gu.se... (primary) (free)
-
visa fler...
-
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...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Nyckelord
- 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
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas