Impartial games emulating one-dimensional cellular automata and undecidability (Q385042): Difference between revisions

In this paper, the focus is placed on connections between combinatorial (two-player take-away) games and (one-dimensional) cellular automata (CA). The 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.