Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655463 | Journal of Combinatorial Theory, Series A | 2013 | 15 Pages |
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