SFI Working Paper Abstract
1997
| Title: | Commuting Cellular Automata |
| Author(s): | Cristopher Moore and Timothy Boykett |
| Files: | [gzipped postscript] [postscript] [pdf] |
| Paper #: | 97-08-076 |
| 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). |