Abstract

This paper studies the capabilities of one dimensional, neighborhood of radius one cellular automata to construct speed one signals. We define the notions of constructibility, consistent constructibility and preserving complexity consistent constructibility. Our main results are the following. There exists a one dimensional neighborhood of radius one cellular automaton with four states which preserving complexity consistently constructs (E*), the set of all speed one signals with a finite number of changes of direction. The class of speed one signal preserving complexity consistently constructed by any one dimensional neighborhood of radius one cellular automaton with three states is a proper subclass of (E*). © 2002 Elsevier Science B.V. All rights reserved.