A simple universal cellular automaton and its one-way and totalistic version. (English) Zbl 0655.68065

Albert, Jürgen; Culik, Karel II

Complex Syst. 1, No. 1, 1-16 (1987).

Summary: 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.

MSC:

68Q80

Cellular automata (computational aspects)

Keywords:

cellular automata; simulation of small universal Turing machines