{
  "id": "1808.08697",
  "version": "v1",
  "published": "2018-08-27T06:05:19.000Z",
  "updated": "2018-08-27T06:05:19.000Z",
  "title": "Universal groups of cellular automata",
  "authors": [
    "Ville Salo"
  ],
  "comment": "Comments welcome!",
  "categories": [
    "math.GR",
    "cs.FL",
    "math.DS"
  ],
  "abstract": "We prove that the group of reversible cellular automata (RCA), on any alphabet $A$, contains a perfect subgroup generated by six involutions which contains an isomorphic copy of every finitely-generated group of RCA on any alphabet $B$. This result follows from a case study of groups of RCA generated by symbol permutations and partial shifts with respect to a fixed full Cartesian product decomposition of the alphabet. For prime alphabets, we show that this group is virtually cyclic, and that for composite alphabets it is non-amenable. For alphabet size four, it is a linear group, while for non-prime non-four alphabets, it is not a subdirect product of linear groups. For all composite alphabets of size at least ten, the group contains copies of all finitely-generated groups of RCA. We also obtain that RCA of biradius one on all large enough alphabets generate copies of all finitely-generated groups of RCA. We ask a long list of questions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-08-27T06:05:19.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cellular automata",
      "universal groups",
      "finitely-generated group",
      "composite alphabets",
      "linear group"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}