CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Impartial games emulating one-dimensional cellular automata and undecidability

Urban Larsson (Institutionen för matematiska vetenskaper, matematik)
Journal of combinatorial theory. Series A (0097-3165). Vol. 120 (2013), 5, p. 1116-1130.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: Cellular automaton, Impartial game, Rule 110, Take-away game, Undecidability

Denna post skapades 2013-04-15. Senast ändrad 2013-05-16.
CPL Pubid: 175710


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)


Diskret matematik

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:

Impartial Games and Recursive Functions