A Simple Universal Cellular Automaton and its One-Way and Totalistic Version
Jürgen Albert
Lehrstuhl für Informatik II,
Universität Würzburg,
D-800 Würzburg, Germany
Karel Culik II
Department of Computer Science
University of Waterloo,
Waterloo, Ontario N2L 3G1, Canada
Abstract
In this paper we first derive two normal form constructions for cellular automata to transform any given (one-dimensional) cellular automaton into one which is one-way and/or totalistic. An encoding of this restricted type of automaton together with any initial configuration becomes the input of our small universal cellular automaton, using only 14 states. This improves well-known results obtained by simulation of small universal Turing machines and also some recent results on universal totalistic cellular automata.
