From heaps of matches to the limits of computability
From MaRDI portal
(Redirected from Publication:396877)
Abstract: We study so-called invariant games played with a fixed number of heaps of matches. A game is described by a finite list of integer vectors of length specifying the legal moves. A move consists in changing the current game-state by adding one of the vectors in , provided all elements of the resulting vector are nonnegative. For instance, in a two-heap game, the vector would mean adding one match to the first heap and removing two matches from the second heap. If , 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 and (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.
Recommendations
- scientific article; zbMATH DE number 2085171
- Limits of computation. An introduction to the undecidable and the intractable
- Seeking computational efficiency boundaries: the Păun's conjecture
- Limits of computation. From a programming perspective
- scientific article; zbMATH DE number 3921983
- Complexity of matching problems
- Exploring the computational content of the infinite pigeonhole principle
- scientific article; zbMATH DE number 6426780
- The limits of fixed-order computation
- Popular matchings and limits to tractability
Cites work
- scientific article; zbMATH DE number 1818513 (Why is no real title available?)
- scientific article; zbMATH DE number 3761989 (Why is no real title available?)
- A generalized diagonal Wythoff Nim
- A mathematical investigation of games of “take-away”
- Cofinite induced subgraphs of impartial combinatorial games: an analysis of CIS-Nim
- Combinatorial games with a pass: a dynamical systems approach
- Complexity, appeal and challenges of combinatorial games
- Extensions and restrictions of Wythoff's game preserving its \(\mathcal P\) positions
- Games, puzzles, and computation
- How far can nim in disguise be stretched?
- Impartial games emulating one-dimensional cellular automata and undecidability
- Invariant and dual subtraction games resolving the Duchêne-Rigo conjecture
- Invariant games
- Lattice games without rational strategies
- Maharaja Nim: Wythoff's queen meets the knight
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Playing games with algorithms: algorithmic combinatorial game theory
- The -operator and invariant subtraction games
- Two variants of Wythoff's game preserving its P-positions
Cited in
(9)- Computational Hardness of Multidimensional Subtraction Games
- A cellular automaton for blocking queen games
- Nonhomogeneous Beatty sequences leading to invariant games
- Subtraction games in more than one dimension
- Combinatorics of \textsc{jenga}
- Taking-and-merging games as rewrite games
- More about Exact Slow $k$-Nim
- Deciding game invariance
- Impartial games emulating one-dimensional cellular automata and undecidability
This page was built for publication: From heaps of matches to the limits of computability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396877)
