This article is cited in 7 papers

On the size of the set of motion rules realizable by cellular automata

G. V. Kalachev^a, E. E. Titova<sup>b

a</sup> Lomonosov Moscow State University
^b Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: A model of motion of a dot on the screen is considered. The screen is a semi-infinite one-dimensional cellular automaton. A particular subset of states of the screen is called the image of the dot. A rule of motion is defined by an infinite sequence of zeros and ones, corresponding respectively to the "stop" and "go" commands. For a broad class of motion rules, an algorithm for implementing the given rule is described. A Bernoulli probability measure of realizable motion rules is explored. It is shown that almost all motion rules are realizable. Also it is shown that the set of realizable motion rules is meager with respect to the product topology.

Keywords: cellular automaton, universal screen, motion of the dot, rule of motion, Bernoulli measure, product topology, Baire category.