Commuting Cellular Automata

Cristopher Moore and Timothy Boykett
Additional contact information
Cristopher Moore: http://www.santafe.edu/~moore

Working Papers from Santa Fe Institute

Abstract: We study the algebraic conditions under which two cellular automata can commute. We show that if either rule is permutive, i.e., one-to-one on its leftmost and rightmost inputs, then the other rule can be written in terms of it; if either rule is a group, then the other is linear in it; and if either is permutive and affine, i.e., linear up to a constant, then the other must also be affine. We also prove some simple results regarding the existence of identities, idempotents (quiescent states) and zeroes (absorbing states).

Date: 1997-08
References: View complete reference list from CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:97-08-076

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().