Article ID Journal Published Year Pages File Type
4655463 Journal of Combinatorial Theory, Series A 2013 15 Pages PDF
Abstract

We study two-player impartial 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 rule 110 games.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics