Computation in Cellular Automata A Selected Review

In this chapter I will review selected topics related to computation in CAs. The presentation will assume an elementary knowledge of the theory of computation. 

Non-Standard Computation. T. GramB, S. Bomholdt, M. GroB, M. Mitchell, T. Pellizzari Copyright 1998 WILEY-VCH Verlag GmbH, Weinheim ISBN 3-527-29427-9 

A C A consists of two components. The first component is a cellular space a lattice of N identical finite-state machines cells), each with an identical pattern of local connections to other cells for input and output, along with boundary conditions if the lattice is finite. Let S denote the set of states in a cell s finite state machine, and A = S denote the number of states per cell. Each cell is denoted by an index i and its state at time t is denoted s (where s G S). The state s of cell i together with the states of the cells to which cell i is connected is called the neighborhood r)l of cell i. 

The second component is a transition rule (or CA rule ) (f r]j) that gives the update state for each cell i as a function of 77.  

Typically in a CA a global clock provides an update signal for all cells at each time step all cells update their states synchronously according to (f rjj). 

---