Communication complexity and intrinsic universality in cellular automata

Eric Goles

Since the pioneering work of von Neumman [15], universality in cellular automata (CA) has received a lot of attention (see [12] for a survey). Historically, the notion of universality used for CA was more or less an adaptation of the classical Turing-universality. Later, a stronger notion called intrinsic universality was proposed: A CA is intrinsically universal if it is able to simulate any other CA [3,9,12] through a uniform and regular encoding based on rescaling. This definition of intrinsic universality may seem very restrictive. However, it can be very common among natural families of CA [1], and allows a complete and precise formalization of the notion of universality.1 As we are going to see, this preciseness, and the robustness of this definition, allows for concrete proofs of negative results and lower bounds. Indeed, in this paper we will explain how to rule out particular elementary cellular automata, as well as whole wellknown classes of cellular automata, from being intrinsically universal, using the elegant framework of communication complexity. In Section 2 we give the basic definitions. One of the key definitions is the following: Given a traditional computational problem P with an arbitrary input w, we can split the input into two subwords w1 and w2; therefore, we can refer to the ‘‘communication complexity’’ of such a problem (w1 is given to Alice while w2 is given to Bob).