From heaps of matches to the limits of computability
type: Item
instance of: scholarly article
title: From heaps of matches to the limits of computability
zbMATH Open document ID: 1295.91024
author: Urban Larsson
author: Johan Wästlund
published in: The Electronic Journal of Combinatorics
publication date: 2014-08-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/1202.0664
full work available at URL: v20i3p41
review text: Summary: We study so-called invariant games played with a fixed number \(d\) of heaps of matches. A game is described by a finite list \(\mathcal{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 \(\mathcal{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) \in \mathcal{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 \(\mathcal{M}\) and \(\mathcal{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.
Mathematics Subject Classification ID: 91A46
Mathematics Subject Classification ID: 68Q80
zbMATH DE Number: 6330313
zbMATH Keywords: combinatorial games
zbMATH Keywords: computational complexity
zbMATH Keywords: logic in computer science
MaRDI profile type: Publication
arXiv ID: 1202.0664
cites work: Q3944542
cites work: How far can nim in disguise be stretched?
cites work: Invariant games
cites work: Extensions and restrictions of Wythoff's game preserving its \(\mathcal P\) positions
cites work: Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
cites work: Lattice games without rational strategies
cites work: Complexity, appeal and challenges of combinatorial games
cites work: Cofinite induced subgraphs of impartial combinatorial games: an analysis of CIS-Nim
cites work: A mathematical investigation of games of “take-away”
cites work: Q3395518
cites work: Two variants of Wythoff's game preserving its \(\mathcal P\)-positions
cites work: A Generalized Diagonal Wythoff Nim
cites work: The \(\star\)-operator and invariant subtraction games
cites work: Impartial games emulating one-dimensional cellular automata and undecidability
cites work: Invariant and dual subtraction games resolving the Duchêne-Rigo conjecture
cites work: Maharaja Nim: Wythoff's queen meets the knight
cites work: Combinatorial games with a pass: A dynamical systems approach
cites work: On Computable Numbers, with an Application to the Entscheidungsproblem
cites work: Q3150942
Recommended article: Q4736394
Recommended article: Q4897685
Recommended article: Seeking computational efficiency boundaries: the Păun's conjecture
Recommended article: Limits of computation. From a programming perspective
Recommended article: Q3696522
Recommended article: Complexity of matching problems
Recommended article: Exploring the computational content of the infinite pigeonhole principle
Recommended article: Q5246016
Recommended article: The limits of fixed-order computation
Recommended article: Popular Matchings and Limits to Tractability
description: scientific article; zbMATH DE number 6330313