Ms: Given a TM M, an initial configuration I M and another configuration C M, will the TM starting from I M ever reach C M? We refer to the CR problem in the context of TMs as CR-TM. In fact, it is this problem for TMs that captures the essence of what can be effectively computed. In particular, by choosing the state component of C M to be one of the halting states (q a or q r ), the problem of determining whether a function is computable is transformed into an appropriate CR-TM problem. By imposing appropriate restrictions on the resources used by a TM (e.g. the number of steps, the number of cells on the work tapes), one obtains different versions of the CR-TM problem which characterize different computational complexity classes [82].

How SDSs
Can Mimic Turing Machines. The above discussion points out an important similarity between SDSs and TMs. Under both of these models, each computational step causes a transition from one configuration to another. It is this similarity that allows one to construct a discrete dynamical system Φ that can simulate a TM. Typically, each step of a TM is simulated by a short sequence of successive iterations Φ. As part of the construction, one also identifies a suitable mapping between the configurations of the TM being simulated and those of the dynamical system. This is done in such a way that the answer to CR-TM problem is "yes" if and only if the answer to the CR problem for the dynamical system is also "yes." To illustrate the basic ideas, we will informally sketch a construction from [4]. This construction produces an SDS Φ that simulates a restricted version of TMs; the restriction being that for any input containing n symbols, the number of work tape cells that the machine may use is bounded by a linear function of n. Such a TM is called a linear bounded automaton (LBA) [82]. Let M denote the given LBA and let n denote the length of the input to M. The domain X for the SDS Φ is chosen to be a finite set based on the allowed symbols in the input to the TM. The dependency graph is chosen to be a simple path on n nodes, where each node serves as a representative for a cell on the input tape. The initial and final configurations C and C ′ for Φ are constructed from the corresponding configurations of M. The local transition function for each node of the SDS is constructed from the given transition function for M in such a way that each step of M corresponds to exactly one step of Φ. Thus, there is a simple bijection between the sequence of configurations that M goes through during its computation and the sequence of states that Φ goes through as it evolves. Using this bijection, it is shown in [4] that the answer to the CR-TM problem is "yes" if and only if Φ reaches C ′ starting from C. Reference [4] also presents a number of sophisticated constructions where the resulting dynamical system is very simple; for example, it is shown that an LBA can be simulated by an SDS in which X is the Boolean field, the dependency graph is d-regular for some constant d and the local transition functions at all the nodes are identical. Such results point out that one does not need complicated dynamical systems to model TM computations.
Barrett et al. [5] have also considered stochastic SDS (SSDS), where the local transition function at each node is stochastic. For each combination of inputs, a stochastic local transition function specifies a probability distribution over the domain of state values. It is shown in [5] that SSDSs can effectively simulate computations carried out by probabilistic TMs (i.e., TMs whose transition functions are stochastic). 5.5. TRANSIMS related questions. Section 2.1.1 gave an overview of some aspects of the TRANSIMS model. The micro-simulator module is specified as a functional composition of four cellular automata of the form ∆ 4 • ∆ 3 • ∆ 2 • ∆ 1. (We only described ∆ 3 which corresponds to velocity updates.) Such a formulation has several advantages. First, it has created an abstraction of the essence of the system in a precise mathematical way without burying it in contextual domain details. An immediate advantage of this specification is that it makes the whole implementation process more straightforward and transparent. While the local update functions for the cells are typically quite simple, for any realistic study of an urban area the problem size would typically require a sequential implementation, raising a number of issues that are best addressed within a mathematical framework like the one considered here.

Mathematical results on finite dynamical systems
In this section we outline a collection of mathematical results about finite dynamical systems that is representative of the available knowledge. The majority of these results are about deterministic systems, as the theory of stochastic systems of this type is still in its infancy. We will first consider synchronously updated systems.
Throughout this section, we make the assumption that the state set X carries the algebraic structure of a finite field. Accordingly, we use the notation k instead of X. It is a standard result that in this case the number q of elements in k has the form q = p t for some prime p and t ≥ 1. The reader may keep the simplest case k = {0, 1} in mind, in which case we are considering Boolean networks.
Recall Equation (4.2). That is, any function g : k n −→ k can be represented by a multivariate polynomial with coefficients in k. If we require that the exponent of each variable be less than q, then this representation is unique. In particular Equation (4.3) implies that every Boolean function can be represented uniquely as a polynomial function.
6.1. Parallel update systems. Certain classes of finite dynamical systems have been studied extensively, in particular cellular automata and Boolean networks. Many of these studies have been experimental in nature, however. Some more general mathematical results about cellular automata can be found in the papers of Wolfram and collaborators [87]. The results there focus primarily on one-dimensional Boolean cellular automata with a particular fixed initial state. Here we collect a sampling of more general results.
We first consider linear and affine systems That is, we consider systems for which the coordinate functions f i are linear, resp. affine, polynomials. (In the Boolean case this includes functions constructed from XOR and negation.) When each f i is a linear polynomial of the form f i (x 1,..., x n ) = a i1 x 1 + · · · + a in x n, the map Φ is nothing but a linear transformation on k n over k, and, by using the standard basis, Φ has the matrix representation where a ij ∈ k for all i, j. Linear finite dynamical systems were first studied by Elspas [30]. His motivation came from studying feedback shift register networks and their applications to radar and communication systems and automatic error correction circuits. For linear systems over finite fields of prime cardinality, that is, q is a prime number, Elspas showed that the exact number and length of each limit cycle can be determined from the elementary divisors of the matrix A. Recently, Hernandez [41] re-discovered Elspas' results and generalized them to arbitrary finite fields. Furthermore, he showed that the structure of the tree of transients at each node of each limit cycle is the same, and can be completely determined from the nilpotent elementary divisors of the form x a. For affine Boolean networks (that is, finite dynamical systems over the Boolean field with two elements, whose local functions are linear polynomials which might have constant terms), a method to analyze their cycle length has been developed in [56]. After embedding the matrix of the transition function, which is of dimension n × (n + 1), into a square matrix of dimension n + 1, the problem is then reduced to the linear case. A fast algorithm based on [41] has been implemented in [44], using the symbolic computation package Macaulay2.
It is not surprising that the phase space structure of Φ should depend on invariants of the matrix A = (a ij ). The rational canonical form of A is a block-diagonal matrix and one can recover the structure of the phase space of A from that of the blocks in the rational form of A. Each block represents either an invertible or a nilpotent linear transformation. Consider an invertible block B. If µ(x) is the minimal polynomial of B, then there exists s such that µ(x) divides x s − 1. Hence B s − I = 0 which implies that B s v = v. That is, every state vector v in the phase space of B is in a cycle whose length is a divisor of s. The cycle structure of the phase space of Φ can be completely determined from the orders of the irreducible factors of the minimal polynomial of Φ. The computation of these orders involves in particular the factorization of numbers of the form q r −1, which makes the computation of the order of a polynomial potentially quite costly. The nilpotent blocks in the decomposition of A determine the tree structure at the nodes of the limit cycles. It turns out that all trees at all periodic nodes are identical. This generalizes a result in [55] for additive cellular automata over the field with two elements.
While the fact that the structure of the phase space of a linear system can be determined from the invariants associated with its matrix may not be unexpected, it is a beautiful example of how the right mathematical viewpoint provides powerful tools to completely solve the problem of relating the structure of the local functions to the resulting (or emerging) dynamics. Linear and affine systems have been studied extensively in several different contexts and from several different points of view, in particular the case of cellular automata. For instance, additive cellular automata over more general rings as state