From heaps of matches to the limits of computability
From MaRDI portal
Publication:396877
zbMATH Open1295.91024arXiv1202.0664MaRDI QIDQ396877FDOQ396877
Authors: Urban Larsson, Johan Wästlund 
Publication date: 14 August 2014
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1202.0664
File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Games, puzzles, and computation
- Playing games with algorithms: algorithmic combinatorial game theory
- Extensions and restrictions of Wythoff's game preserving its \(\mathcal P\) positions
- Complexity, appeal and challenges of combinatorial games
- Lattice games without rational strategies
- Impartial games emulating one-dimensional cellular automata and undecidability
- The \(\star\)-operator and invariant subtraction games
- A mathematical investigation of games of “take-away”
- How far can nim in disguise be stretched?
- Cofinite induced subgraphs of impartial combinatorial games: an analysis of CIS-Nim
- Maharaja Nim: Wythoff's queen meets the knight
- Two variants of Wythoff's game preserving its \(\mathcal P\)-positions
- A generalized diagonal Wythoff Nim
- Combinatorial games with a pass: a dynamical systems approach
- Invariant and dual subtraction games resolving the Duchêne-Rigo conjecture
- Invariant games
Cited In (9)
- Computational Hardness of Multidimensional Subtraction Games
- A cellular automaton for blocking queen games
- Subtraction games in more than one dimension
- Nonhomogeneous Beatty sequences leading to invariant games
- 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)
