Impartial games emulating one-dimensional cellular automata and undecidability

DOI10.1016/J.JCTA.2013.02.009MaRDI QIDQ385042zbMATH OpenOpenAlexFDO

Authors Urban Larsson

Publication date 29 November 2013

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.1039

zbMATH Keywords

cellular automatonimpartial gamePascal trianglerule 110rule 60take-away gametriangle-placing gamesundecidability

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) 2-person games (91A05) Combinatorial games (91A46)

Abstract: We study two-player emph{take-away} games whose outcomes emulate two-state one-dimensional cellular automata, such as Wolfram's rules 60 and 110. Given an initial string consisting of a central data pattern and periodic left and right patterns, the rule 110 cellular automaton was recently proved Turing-complete by Matthew Cook. Hence, many questions regarding its behavior are algorithmically undecidable. We show that similar questions are undecidable for our emph{rule 110} game.

Review text

In this paper, the focus is placed on connections between combinatorial (two-player take-away) games and (one-dimensional) cellular automata (CA).NEWLINENEWLINEThe author considers a variation of the subtraction game: the number of tokens a player is allowed to remove depends on the previous player's move. As an introduction, the author studies a take-away game that emulates Wolfram's rule \(60\). Then, triangle-placing games are introduced. They emulate an infinite class of CA. Also it is shown that these games have the same equivalent outcomes (or winning strategies) as a class of take-away game. Finally, undecidability result for CA and rule \(110\) are interpreted in terms of combinatorial games.

Recommendations

• scientific article; zbMATH DE number 8789
• scientific article; zbMATH DE number 1944403
• From heaps of matches to the limits of computability
• A cellular automaton for blocking queen games
• scientific article; zbMATH DE number 1241089

Cites work

• 2-pile Nim with a restricted number of move-size imitations
• A concrete view of Rule 110 computation
• A mathematical investigation of games of “take-away”
• Blocking Wythoff Nim
• Computation theory of cellular automata
• From heaps of matches to the limits of computability
• Games, puzzles, and computation
• scientific article; zbMATH DE number 988843 (Why is no real title available?)
• scientific article; zbMATH DE number 1818513 (Why is no real title available?)
• scientific article; zbMATH DE number 3896307 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2188483 (Why is no real title available?)
• scientific article; zbMATH DE number 3339030 (Why is no real title available?)
• Lattice games without rational strategies
• Playing games with algorithms: algorithmic combinatorial game theory
• The -operator and invariant subtraction games
• Universality in elementary cellular automata

Cited in

(7)

• Taking-and-merging games as rewrite games
• From heaps of matches to the limits of computability
• scientific article; zbMATH DE number 8789 (Why is no real title available?)
• scientific article; zbMATH DE number 1944403 (Why is no real title available?)
• Combinatorics of \textsc{jenga}
• A cellular automaton for blocking queen games
• A cellular automaton for blocking queen games

This page was built for publication: Impartial games emulating one-dimensional cellular automata and undecidability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q385042)