Fishwick P.A. (editor) Handbook of Dynamic System Modeling
Подождите немного. Документ загружается.
20-10 Handbook of Dynamic System Modeling
and the corresponding TL formulation is 22α → 2α. Note the relationship between this and (Ax4),
reflecting the status of transitivity and density as mutually converse. An equivalent formulation of density
is
3α →
33α.
A dense model of time corresponds well to our normal practice of identifying positions in the time
series by means of numbers. Given times t
1
and t
2
identified as, say, exactly 10 and 11 s, respectively after
some agreed“zero” time t
0
, then if we assume the existence of a time t corresponding to 10.5 seconds after
t
0
we are in effect making use of the density property. Further applications of density then allow us to
bring in times at 10.25 and 10.75 s, then 10.125, 10.375, 10.625, 10.875 s, and so on, there being no limit,
on this picture, to how finely the time line can be subdivided.
For some purposes, however, it is more convenient to regard time as proceeding in discrete steps
rather than a continuous flow. An example is when modeling the execution of a computer program,
where nothing significant, from the point of view of the program, occurs between successive steps of the
execution. Another example would be a game such as chess, where what matters is the configuration of
the board after each successive move, forming a discrete series of times that are relevant. Such discrete
time series can still be marked off using numbers, only now the appropriate number system to use is the
integers (
Z, <) rather than the real numbers (R, <).
A discrete-temporal frame has the two properties
∀t∀t
(t
≺ t →∃t
(t
≺ t ∧¬∃u(t
≺ u ∧ u ≺ t))) (PDisc)
∀t∀t
(t ≺ t
→∃t
(t ≺ t
∧¬∃u(t ≺ u ∧u ≺ t
))) (FDisc)
Thus (FDisc) says that if t is followed by any time at all, then it has an immediate successor t
characterized
by the fact that there is no time between t and t
. Similarly, (PDisc) says that any point with a predecessor
has an immediate predecessor. We use (Disc) to denote the conjunction of these two formulae.
It can be shown that there is no tense logic formula that exactly characterizes discreteness (see Van
Benthem, 1983).
9
However, the discreteness of the temporal frame can be implicitly incorporated into a
TL by extending the language. A new temporal operator , called the Next-time operator, is introduced,
interpreted so that α is true at time t just if α is true at the immediate successor time, which we may
denote t +1 on the assumption that integers are used to label the times in the model.
20.4.7 Combinations of Properties
Certain combinations of the above-mentioned properties are noteworthy. The combination (Trans, Irref,
Lin, Unb) corresponds to the intuition of time as a line extending indefinitely far back into the past (“no
beginning”) and indefinitely far into the future (“no end”). We may add to this combination either (Dens)
or (Disc), the resulting combinationsbeing labeled DE and DI, respectively (Van Benthem, 1983). In neither
case do we end up specifying the flow of time completely. DE, for example, holds for both a real (
R, <)
and a rational (
Q, <) time line; to identify (R, <) uniquely we need a second-order formula (expressing
Dedekind continuity). Gabbay et al. (1994) give the following pair of TL formulae to express this:
FGα ∧F¬α ∧G(¬α → F¬α) → F(Gα ∧¬PGα)
PHα ∧P¬α ∧H(¬α → P¬α) → P(Hα ∧¬FHα)
Likewise, while the most natural model for DI is (
Z, <), others are possible, e.g., two copies of
Z,one
after the other. To identify (
Z, <) uniquely, we need a second-order condition (given (Disc), Dedekind
continuity suffices again).
9
Note, however, that if the temporal frame is assumed to be linear, then the formulae GPα →α ∨Pα and
HFα →α ∨Fα together secure discreteness as well. For, to take the second formula, if t does not have an imme-
diate predecessor, then letting α be true at all predecessors of t and at no other times, we see that HFα is true at t (since
every point in the past of t has a point in its future which is still in the past of t), but α ∨Fα is false at t.
Temporal Logic 20-11
20.5 Further Extensions to the Formal Language
An important addition to the expressive power of TL was made by Kamp (1968) who introduced new
temporal operators S and U, read “since” and “until.” Syntactically, these are binary operators, acting on a
pair of propositions rather than a single one as in the case of P and F. As binary operators, they may be
treated either as prefixes (e.g., “Spq”) or as infixes (e.g., “pSq”)—both conventions have been used; here
we use infix notation to emphasize the reading of “pSq”as“p since q” (and likewise with U).
The semantic rules for the new operators are
•
(T, ≺, t) |= αSβ if and only if, for some t
∈ T, t
≺ t,(T, ≺, t
) |= β and, for every t
∈ T,if
t
≺ t
t then (T, ≺, t
) |= α
•
(T, ≺, t) |= αUβ if and only if, for some t
∈ T, t ≺ t
,(T, ≺, t
) |= β and, for every t
∈ T,if
t t
≺ t
then (T, ≺, t
) |= α.
Thus, αSβ says that β was true at some past time, and α has been true ever since then, up to and including
the present. Similarly, αUβ says that β will be true at some future time, but until then, α will always
be true.
A weak variant of U that is sometimes used is the operator U
W
, perhaps misleadingly read “unless,”
defined so that αU
W
β is equivalent to αUβ ∨Gα, meaning that α will be true until such time as β becomes
true—there being no requirement for this ever to happen. In the case that β never becomes true, α must
remain true forever, as indicated by the second disjunct.
The significance of these new operators is that, subject to certain assumptions about the model of time,
they bring the expressive power of the logic up to that of the FOL of time. For example, over linear discrete
time, or linear continuous time, for any first-order temporal formula φ(t), there is an S, U-TL formula α
which holds at all and only those times t for which φ(t). That we need S and U follows from the fact that
these operators cannot be defined in terms of P, F, G, and H—that is, no formula constructed using these
four operators is equivalent to either pSq or pUq.
In contrast the other operators can be defined in terms of S and U. To do this, it is convenient to
introduce formulae ⊥ and that are defined to be always true (i.e., equivalent to α ∨¬α) and always
false, respectively (equivalent to α ∧¬α). Then we can define Pα as Sα, and Fα as Uα, with H and
G then defined as ¬P¬ and ¬F¬
, respectively. The formula Sα says that α was true at some past time,
since when has always been true. Since the latter clause must hold in any case, the statement reduces to
an assertion that α was true at some past time—i.e., Pα; and likewise with U and F.
20.6 Illustrative Examples
In this section, we provide some brief illustrations of a range of possible applications of TL. The area in
which it has been most widely used, and which has provided the main stimulus to its development, is in the
specification and verification of concurrent computer programs, as illustrated in Section 20.6.2. However,
similar considerations, concerning sequencing, scheduling, and temporal constraint satisfaction, can arise
in the specification of any system which evolves through time, and in Section 20.6.3 we mention a couple
of examples to illustrate this.
20.6.1 A System with an Attractor
Suppose we have a system with just three states; these can be represented by three mutually exclusive
formulae P, Q, and R, with the understanding that each of the formulae is true just when the state it
represents holds. The dynamics of the system are such that whenever it is in state P, it will eventually enter
state Q, and whenever it is in state Q it will eventually enter state R. Moreover, state R is an attractor state,
i.e., once the system has entered it, it can never leave it. With a little reflection it seems obvious that that the
20-12 Handbook of Dynamic System Modeling
system will eventually enter state R and stay there. One might, naively, illustrate this with a state sequence
such as
PPPPPPPQQQQQQQQQQQQQRRRRRRRRRRRRRRRR ...
but this is only illustrative since in reality there is an infinite number of possible state sequences for this
system, another one being, for example
PPPPQPPQPPQQQQPQPPPQQRRRRRRRRRRRRRRR ...
The state sequences illustrated here implicitly presuppose a discrete linear time, but is either of these
properties necessary for the desired result to follow? TL can help us to determine exactly what underlying
assumptions are required for the reasoning to go through correctly.
To establish the desired conclusion, we can formulate the problem in TL as follows. Our description
of the system dynamics corresponds to the following four formulae (we use
2, 3 notation since we are
reasoning forward in time):
2(P ∨Q ∨ R) (20.14)
2(P → 3Q) (20.15)
2(Q → 3R) (20.16)
2(R → 2R) (20.17)
From these we have to derive the formula
32R. Without writing out the full formal derivation, we can
indicate the lines along which it proceeds as follows.
We know from Eq. (20.14) that at any time in the system’s evolution we have P ∨ Q ∨ R. Several
applications of Eq. (20.15), Eq. (20.16), and Eq. (20.17) enable us to derive from this the formula
332R ∨32R ∨2R. Togetfromhereto32R we need the following assumptions:
33α → 3α (20.18)
2α → 32α (20.19)
Assumption Eq. (20.18) is equivalent to (Ax4), the transitivity axiom. Given transitivity, Eq. (20.19) may be
derived from
22α →32α, which in turn is an instance of (FUnb). We have thus laid bare the assumptions
underlying our intuitive reasoning: the flow of time is transitive and unbounded in the future. There is
no need to assume linearity, density, discreteness, or any of the other conditions we might suppose to
be required (and which may be present in the mental models we construct in the course of our intuitive
reasoning).
20.6.2 Application to Reasoning about Programs
TL has been considered the most appropriate logic for reasoning about the behavior of reactive programs—
that is, programs which maintain an ongoing interaction with the environment rather than delivering a
final output and then halting. Commonly cited examples of reactive programs include computer operating
systems, airline reservation systems, and many e-business systems. One area in which it is important
to be able to reason correctly about the behavior of such systems is correctness: how can we be sure
that the program as implemented actually behaves in the manner required by its specification? Among
the correctness properties of programs we may distinguish safety properties, informally characterized
as ensuring that “nothing bad happens,” and liveness properties, ensuring that “something good will
happen.”
10
In TL terms, safety properties are typically expressed using formulae of the form 2α, while
liveness properties are expressed using
3α.
10
These terms, and the associated slogans, are due to Lamport (1977).
Temporal Logic 20-13
To illustrate these ideas with a simple example, suppose that we have a number of concurrent processes
which have to apply to some resource allocator for the use of various resources.
11
We introduce the
following primitive propositions to describe this situation:
Available(i) says that resource i is unallocated.
Granted(i, j) says that process i is granted use of resource j.
Requesting(i, j) says that process i is requesting use of resource j.
Using(i, j) says that process i is using resource j.
The following are all safety properties:
•
A process cannot request a resource which it is already using
2(Using(i, j) →¬Requesting(i, j))
•
A process cannot use a resource which it has not been granted
2(Using(i, j) → Granted(i, j))
•
Two processes cannot simultaneously use the same resource
2¬(Using(i, j) ∧Using(i
, j) ∧i = i
)
The following are liveness properties:
•
If a process requests use of a resource, it is eventually granted it
2(Requesting(i, j) → 3Granted(i, j))
•
If a process is granted a resource, it will eventually use it
2(Granted(i, j) → 3Using(i, j))
•
If a process is using a resource, it will eventually release it
2(Using(i, j) → 3¬Using(i, j))
These are just a sample of the system requirements that can be expressed as TL formulae. A complete
set of such formulae may constitute a formal specification for a system to exhibit the desired behavior.
This can be used in various ways: it provides a standard to which any implementation of the program
must adhere, and temporal reasoning may be used to verify that a given implementation does indeed meet
the specification. To do this, it is necessary to show that the formulae in the specification hold for every
possible execution sequence of the program (see Manna and Pnueli, 1981). A related goal is to use the
specification as a starting point from which to synthesize the synchronization skeleton of a program, as
indicated in (Section 20.4.4).
20.6.3 Other Applications
The extremely general nature of TL formalism means that in principle it should be applicable to a wide
range of situations in which it is necessary to specify or control the behavior of systems evolving through
time. Here we mention just two examples.
In artificial intelligence, TL has been used by Bacchus and Kabanza (1996) as a means for controlling
search in a forward-chaining planner, thereby at least mitigating the combinatorial explosion to which
such planners are inevitably prone. Their approach is implemented in a system called TLPlan, which uses a
first-order linear temporal logic, LTL for expressing strategies tailored to the chosen planning domain—an
example being the formula
∀[x : object(x)]
2(polish(x) ∧¬polish(x) →2¬polish(x))
which “prohibits action sequences where an object is polished twice.”
In a very different setting, Wood (1989) used TL to specify the operation of a bank of identical elevators
servicing a number of floors in a building. This was approached in the spirit of a case study to investigate
the suitability of TL for this kind of work; the author’s conclusion is largely positive, including the
11
This example is adapted from Pnueli (1985).
20-14 Handbook of Dynamic System Modeling
statement that TL specification is “a splendid vehicle for communicating precisely the behavior of the
elevator system.” Examples of temporal formulae used are
∀i, m
2(¬flDoorsClosed(i, m) ↔¬elDoorsClosed(i) ∧elPosition(i, m))
which states that at all times, the door for accessing elevator i on the mth floor will be open if and only if
elevator i is at the mth floor and its doors are open; and
∀i, m(dormant(i, m) ∧ elDestLit(i, m) →¬elDoorsClosed(i))
which says that if elevator i is in a dormant condition at the mth floor and the user pushes the destination
button for the mth floor in that elevator, then the elevator doors will open immediately afterwards (note
the use of the “next time” operator to express this, implying a discrete model of time).
20.7 Conclusion
We have introduced TL, a system for reasoning about the dynamical properties of the world by manipu-
lating formulae expressed in a formal language specifically designed to allow different properties to hold
at different times. We described the formalism from both a syntactic and a semantic point of view, and
introduced a range of different varieties of TL, adapted to working with a range of different models of
time. Some applications were briefly described. Owing to the introductory nature of the chapter, much of
importance has inevitably been left out, and the reader interested in pursuing the topic is encouraged to
consult the references recommended in the next section.
20.8 Further Reading
There is a voluminous literature on TL, emanating from several distinct (though overlapping) research
communities, notably computer science, mathematics, logic, and philosophy, with a correspondingly wide
range of focus. Much of this literature appears in the form of journal articles or conference proceedings,
but over the years a number of books have been produced on the subject, some of which have been very
influential.
In the philosophical tradition, the seminal work (Prior, 1967) still retains much of interest to the modern
reader, although its readability is somewhat compromised by the use of “Polish” prefix notation for the
logical operators. This notation is largely unfamiliar to present-day readers, who may have the feeling of
having to decipher the formulae rather than read them; but this has been remedied in the later work (Prior,
1968), which has been recently reissued with all the formulae rewritten in the more familiar infix notation
(Prior, 2003). An important work exploring the logical and mathematical properties of models of time
and their logics, with many interesting philosophical sidelights, is Van Benthem (1983).
For the computer science perspective, some useful works to consult are Galton (1987), Goldblatt (1987),
and Bolc and Szałas (1995). A detailed survey, with many references, is provided by Emerson (1990). More
technical, but containing a wealth of useful material and many stimulating observations, is Gabbay et al.
(1994). A sample of recent research, covering many aspects of TL, is Barringer et al. (2000). A still more
recent compilation with an emphasis on applications to artificial intelligence—but with much of interest
in a wider setting—is Fisher et al. (2005).
For the reader interested in the history of TL, Øhrstrøm and Hasle (1995) is recommended, although it
should be noted that the applications in computer science are largely neglected.
An important forum for the dissemination of research in TL is provided by a series of international
symposia on Temporal Representation and Reasoning entitled simply TIME, first held in Florida in 1994
and still going strong at the time of writing.
Temporal Logic 20-15
References
Bacchus, F. and F. Kabanza (1996). Using temporal logic to control search in a forward-chaining planner.
In M. Ghallab and A. Milani (Eds.), New Directions in AI Planning, pp. 141–153. Amsterdam: IOS
Press.
Barringer, H., M. Fisher, D. Gabbay, and G. Gough (Eds.) (2000). Advances in Temporal Logic, Volume 16
of Applied Logic Series. Dordrecht: Kluwer.
Bolc, L. and A. Szałas (Eds.) (1995). Time and Logic: A Computational Approach. London: UCS Press.
Dowty, D. (1979). Word Meaning and Montague Grammar. Dordrecht: D. Reidel.
Emerson, E. A. (1990). Temporal and modal logic. In J. van Leeuwen (Ed.), Handbook of Theoretical
Computer Science (Volume B: Formal Models and Semantics), pp. 995–1072. Amsterdam: Elsevier.
Emerson, E. A. and E. M. Clarke (1982). Usingbranching time temporal logic to synthesize synchronisation
skeletons. Science of Computer Programming 2, 241–266.
Fisher, M., D. Gabbay, and L. Vila (Eds.) (2005). Handbook of Temporal Reasoning in Artificial Intelligence.
New York: Elsevier.
Gabbay, D. M., I. Hodkinson, and M. Reynolds (Eds.) (1994). Temporal Logic: Mathematical Foundations
and Computational Aspects. Oxford: Oxford University Press.
Galton, A. (Ed.) (1987). Temporal Logics and Their Applications. London: Academic Press.
Goldblatt, R. (1987). Logics of Time and Computation. Stanford, CA: Center for the Study of Language and
Information.
Hodges, W. (2001). Logic. London: Penguin Books.
Jeffrey, R. C. (2006). Formal Logic: Its Scope and Limits (Fourth edition). Indianapolis: Hackett Publishing.
Kamp, J. A. W. (1968). Tense Logic and the Theory of Linear Order. Ph.D. thesis, University of California,
Los Angeles.
Lamport, L. (1977). Proving the correctness of multiprocess programs. IEEE Transactions on Software
Engineering SE-3, 125–143.
Lamport, L. (1980). “Sometime” is sometimes “not never”: On the temporal logic of programs. In
Proceedings of the 7th ACM Symposium on Principles of Programming Languages, pp. 174–85.
Manna, Z. and A. Pnueli (1981). Verification of concurrent programs: The temporal framework. In
R. S. Boyer and J. S. Moore (Eds.), The Correctness Problem in Computer Science, pp. 215–273.
London: Academic Press.
Moszkowski, B. (1986). Executing Temporal Logic Programs. Cambridge: Cambridge University Press.
Øhrstrøm, P. and P. F. V. Hasle (1995). Temporal Logic: From Ancient Ideas to Artificial Intelligence.
Amsterdam: Kluwer.
Pnueli, A. (1985). Applications of temporal logic to the specification and verification of reactive systems:
A survey of current trends. In J. W. de Bakker, W.-P. de Roever, and G. Rozenberg (Eds.), Current
Trends in Concurrency, Volume 224 of Lecture Notes in Computer Science, pp. 510–584. Berlin:
Springer.
Prior, A. N. (1967). Past, Present, and Future. Oxford: Clarendon Press.
Prior, A. N. (1968). Papers on Time and Tense. Oxford: Clarendon Press.
Prior, A. N. (2003). Papers on Time and Tense. Oxford: Oxford University Press. (New edition, edited by
Per Hasle, Peter Øhrstrøm, Torben Bräuner, and Jack Copeland.)
Van Benthem, J. F. A. K. (1983). The Logic of Time Second edition, 1991. Dordrecht: Kluwer.
Wood, W. G. (1989). Temporal logic case study. Technical Report CMU/SEI-89-TR-024, Carnegie Mellon
Software Engineering Institute.
21
Modeling Dynamic
Systems with Cellular
Automata
Peter M.A. Sloot
University of Amsterdam
Alfons G. Hoekstra
University of Amsterdam
21.1 Introduction....................................................................21-1
21.2 A Bit of History...............................................................21-2
21.3 Cellular Automata to Model Dynamical Systems..........21-3
21.4 One-Dimensional CAs....................................................21-3
21.5 Lattice Gas Cellular Automata Models of
Fluid Dynamics...............................................................21-5
The Road to Lattice Gas Cellular Automata
•
LGCA and
Fluid Dynamics
•
Simulating an LGCA
•
Some
Applications
•
Lattice Boltzmann Method
21.1 Introduction
In modeling dynamic systems, one of the first questions to be answered is whether the involved processes
can be viewed to be discrete in state, time, space, or continuous. The model choice should be robust with
respect to the chosen space–time–state framework. Table 21.1 gives a selective overview of the various
modeling approaches.
In this chapter, we focus on complete discrete model systems: cellular automata (CAs). CAs are decen-
tralized spatially extended systems consisting of large numbers of simple and identical components with
local connectivity. Such systems have the potential to perform complex computations with a high degree
of efficiency and robustness as well as to model the behavior of complex systems from nature. CAs have
been studied extensively in the natural sciences, mathematics, and computer science. They have been
considered as mathematical objects about which formal properties can be proved and have been used as
parallel computing devices, both for high-speed simulation of scientific models and for computational
TABLE 21.1 Mathematical and numerical modeling approaches to spatio-temporal processes.
Model/Variable State Space Time
PDEs C C C
Integro-difference equations C C D
Coupled ODEs C D C
Interacting particle systems D D C
Coupled map lattices, systems of difference equations, LBE models C D D
Cellular automata and lattice gas automata D D D
PDE, partial differential equation; ODE, ordinary differential equation; LBE, lattice Boltzmann
equation. For more details see Berec (2002) and Deutsch and Dormann (2004).
21-1
21-2 Handbook of Dynamic System Modeling
tasks such as image processing. CAs have also been used as abstract models for studying “emergent”
cooperative or collective behavior in complex systems (e.g., Sloot, 2001b). In addition, CAs have been
successfully applied to the simulation of a large variety of dynamical systems such as biological processes
including pattern formation, earthquakes, urban growth, galaxy formation, and most notably in studying
fluid dynamics. Their implicit spatial locality allows for very efficient high-performance implementations
and incorporation into advanced programming environments. For a selection of the numerous papers in
all of these areas, see, e.g., Bandini (2002), Burks (1970), Deutsch and Dormann (2004), Farmer et al.
(1984), Forrest (1990), Frisch et al. (1986), Ganguly et al. (2003), Gutowitz (1990), Jesshope et al. (1994),
Kaandorp et al. (1996), Mitchell (1998), Naumov (2004), Sloot (1999), Sloot and Hoekstra (2001), Sloot
et al. (1997, 2001c, 2002, 2004), and Wolfram (1986a, 1986b, 2002).
In this chapter, we will give some background on CA modeling and simulation of dynamical systems
with an emphasis on simulating fluid dynamics.
21.2 A Bit of History
In 1948, on the occasion of the Hixon Symposium at Caltech, John von Neumann gave a lecture entitled
“The General and Logical Theory of Automata” (von Neumann, 1951, 1966), where he introduced his
thoughts on universal,self-reproducing machines, trying to develop an abstract model of self-reproduction
in biology, a topic that had emerged from investigations in cybernetics (Wolfram, 2002, 876 ff). von
Neumann himself said to have been inspired by Stanislaw Ulam (1952, 1962) and Turing’s theory of
universal automata, which dates back another 10 years (Turing, 1936). Some scientists regard the paper by
Wiener and Rosenblueth (1946) as the start of the field (Wolf-Gladrow, 2000), or mathematical work that
was done in the early 1930s in Russia.
So we see that the roots of CA may be traced back to biological modeling, computer science, and
(numerical) mathematics. From the early days of von Neumann and Ulam up to the recent book of
Wolfram, CAs have attracted researchers from a wide variety of disciplines. It has been subjected to
rigorous mathematical and physical analysis for the last 50 years, and its application has been proposed
and explored in almost all branches of science. A large number of research papers are published every year.
Specialized conferences, such as Sloot et al. (2004),Automata (2005), and NKS (2005), and special issues of
various journals on CA have been initiated in the last decades. Several universities started offering courses
on CA. The reason behind the popularity of CA can be traced to their simplicity and to the enormous
potential they hold in modeling complex systems, in spite of their simplicity. Or in the words of R. May:
“We would all be better off if more people realized that simple dynamical systems do not necessarily lead to
simple dynamical behavior” (May, 1976). This has led to some very remarkable claims and predictions by
renowned researchers about the potential of CAs. In this respect, we came across the following statements
that are worth mentioning:
The entire universe is being computed on a computer, possibly a cellular automaton.
Konrad Zuse, as he referred to this as “Rechnender Raum” (Zuse, 1967, 1982)
I am convinced that CA, in one form or another will eventually be found lurking at the very heart of how
the universe really works
Andrew Ilachinski (2001)
The view of the Universe as a cellular automaton provides the (same) perspective, (i.e.,) that reality
ultimately is a pattern of information.
Ray Kurzweil (2002)
I have come to view [my discovery] as one of the more important single discoveries in the whole history
of theoretical science
Stephan Wolfram: Talking about his CA work in his NKS book (Wolfram, 2002)
Modeling Dynamic Systems with Cellular Automata 21-3
The remainder of this chapter is organized as follows, we start with a formal description of CA and
some of their spatio-temporal properties and we will briefly discuss their capacity to model dynamical
systems. Next we will focus on the use of CAs to model fluid flow, starting from Lattice Gas CAs up to
recent developments in the related Lattice Boltzmann Method for fluid flow.
21.3 Cellular Automata to Model Dynamical Systems
In general, a CA is specified by the following four characteristics:
•
A discrete lattice L: This is the discrete lattice of cells (nodes and sites) upon which the CA dynamics
unfolds.
L ⊂ R
D
•
consists of a set of cells that homogeneously cover a D-dimensional Euclidian
space.
L can have any dimension“D”(normally 1, 2, or 3), with well-defined boundary conditions.
•
A finite state space: Each cell can assume only one of a finite number of different values:
σ
i∈L
(t) ∈ ≡{0, 1, 2, ···, k −1},whereσ
i
is the value of the ith cell at time t, and is usually
taken to be the set of integers modulo k,
Z
k
(formally any finite commutative ring will do). For a
finite lattice of
N cells, the total number of global states is also finite and given by k
N
.
•
Boundary conditions: Boundary conditions play an important role in CA dynamics. Although CA
are defined on infinite large lattices, computer simulations impose finite sets. Common boundary
conditions are periodic (i.e., the lattice is repeated periodically in each direction, in effect wrapping
the boundaries onto each other in each direction), reflecting (i.e., boundary values are reflected back
into the lattice), and fixed (i.e., the boundary values have a prescribed fixed value).
•
Dynamical update and transition Rule φ:
φ: × ×···×
n
→,wheren is the number of cells that defines the “neighborhood” of a
given cell i. With
S
i
to be the sublattice neighborhood about cell i, the transition rule is given by
σ
i
(t +1) =φ(σ
j
(t) ∈S
i
).
The spatial arrangement of the cells is specified by the nearest neighbor connection links, obtained by
joining pairs of cells. State transitions are local in both space and time. Individual cells evolve iteratively
according to a fixed (often deterministic) function of the current state of that cell and its neighboring cells.
One iteration step of the dynamical evolution is achieved after synchronous (i.e., simultaneous in time)
application of the rule φ to each cell in the lattice
L.
21.4 One-Dimensional CAs
The general form of a one-dimensional (1D) CA rule φ with an arbitrary range ‘r’isgivenbyσ
i
(t +1) =
φ(σ
i−r
(t), ..., σ
i
(t), ..., σ
i+r
(t)); with φ:
2r+1
→ ,whereσ
j
∈{0, 1, ..., k − 1}, and φ is explicitly
defined by assigning values to each of the k
2r+1
possible (2r +1)-tuples of possible configurations for a
given sublattice neighborhood
S
i
. From this we see that we have a total of k
k
2r+1
possible rules in a 1D CA.
So for a binary state 1D CA, with nearest neighbor interaction, there are 256 (2
2
3
) possible rules.
The boundary conditions imposed in a 1D CA can be
•
Periodic: When the left boundary cell is kept identical to the most right (normal) cell, and the right
boundary cell is kept identical to the most left (normal) cell.
•
Reflecting: When the left boundary cell is kept identical to the most left (normal) cell, and the right
boundary cell is kept identical to the most right (normal) cell.
•
Fixed: When the boundary cells are set to a fixed value.
The system dynamics of the CA is determined by the local transition rule φ, which can be spatial homo-
geneous (independent of cell position), or inhomogeneous (for instance in the case of fixed boundary
conditions shown in Figure (21.1). Furthermore, the update can be time dependent or time independent,