Impartial games emulating one-dimensional cellular automata and undecidability (Q385042)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Impartial games emulating one-dimensional cellular automata and undecidability |
scientific article; zbMATH DE number 6234599
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Impartial games emulating one-dimensional cellular automata and undecidability |
scientific article; zbMATH DE number 6234599 |
Statements
Impartial games emulating one-dimensional cellular automata and undecidability (English)
0 references
29 November 2013
0 references
cellular automaton
0 references
impartial game
0 references
take-away game
0 references
rule 110
0 references
rule 60
0 references
undecidability
0 references
triangle-placing games
0 references
Pascal triangle
0 references
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.
0 references
