Basic Definitions

Introduction

Cellular Automata (CAs) are discrete dynamic systems that exhibit chaotic behavior and self-organization and lend themselves to description in rigorous mathematical terms. The main aim of this chapter is to introduce CAs from a formal perspective. Ever since the work of von Neumann (1966), von Neumann & Burks (1970), Toffoli & Norman (1987), Wolfram (1983; 1984), and Langton (1984; 1986; 1990), specialists have recognized CAs as a model of crucial importance for complexity studies. Like other models used in the investigation of complex phenomena (Chua & Yang, 1988; Chua, 1998), a CA consists of a number of elementary components, whose interactions determine its dynamics. In this and the following chapters, we will sometimes refer to these elementary components as cells, sometimes as sites. The cells of a CA can be positioned along a straight line or on a 2 or 3-dimensional grid, creating 1-D, 2-D and 3-D CAs. Automata consisting of cells whose only possible states are 0 or 1, are Boolean Automata; automata whose cells can assume more than 2 states are multi-state CAs. In both cases, the CA contains “elementary particles” whose dynamics are governed by simple rules. These rules determine sometimes unpredictable, emergent behaviors, ranging from the simple, through the complex to the chaotic. The basic parameters determining these behaviors are the number of “neighbours” affecting the behavior of a cell, the size and geometry of the area surrounding the cell (its “neighborhood”), the states cells are allowed to assume and the local rules determining their dynamics. All the cells in a CA are governed by the same rules which they use to interpret their own state and that of their neighbours and to decide the next step in their development. In the models considered here, each cell reads the state of its neighbours and determines it own state, simultaneously with the other cells. This kind of CA is thus a kind of parallel computer. Boolean 1-D CAs, in which each cell has a neighbourhood of three cells, are known as Elementary Cellular Automata (ECAs). Recent fine work from Chua (2006; 2007) and his co-workers (Chua et al., 2002; Chua et al. 2004) shows that although ECAs have been studied for a long time (Wolfram, 1984; 2002; Wuensche & Lesser 1992), they can still offer surprises. Wolfram (2002), has argued that ECAs already show the most important features of the complex behavior of higher dimensional and multi-state CAs. We believe, however, that this is not entirely true. In particular, ECAs do not show the same kinds of complex behavior seen in multi-state automata. Even more importantly, they do not display self-replication except in a rudimentary form. As we will see in later chapters, ECAs cannot generate the complex structures and geometries generated by self-reproducing CAs operating in higher dimensions. In the final part of this chapter, we describe the way these patterns are organized in time and space, and give examples of the extreme complexity and beauty to which they often give rise (Bilotta & Pantano, 2006).

A number of authors have analyzed CAs with continuous valued states, CAs that evolve asynchronously, non-homogeneous CAs, CAs with probabilistic rules, etc. (Sipper et al., 1997; Nehaniv, 2002; Fatès & Morvan, 2005; Fatès et al., 2006). For a review of the literature see Wolfram (2002). A number of researchers have used generalizations of CAs to model physical phenomena on different scales (Hoekstra et al., 2008). In this book, we will describe models of biological phenomena based on CAs with discrete states that evolve synchronously. By contrast, asynchronous are highly complex and difficult to control. We will touch on these processes only in Chapter 13, when we compare replication in a synchronous CA with emergent replication in an asynchronous process.