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

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.