×

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

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)
PDF BibTeX XML Cite