Cellular automata can represent real-world phenomena studied in physics and biology, and have been applied to intelligent systems like arti cial life and multi-agent systems. In this paper, we study a semantic preserving transformation between cellular automata and normal logic programs based on the TP -operator. In particular, a subset of normal logic programs is shown to precisely correspond to the classic grid-based cellular automata such as Conway's Game of Life. We use two automaton models: one-way bounded cellular automata, for simplicity of construction, and unbounded cellular automata, which correspond to the classic de nition of grid-based cellular automata. Using this construction, some computational theorems are easily proved regarding phenomena in the con gurations of one-way bounded cellular automata, and some decidability results are newly obtained on the orbits of normal logic programs.
The study of dynamic systems has become more and more important recently,
especially in the context of simulation and prediction of complex, physical or biological
systems. One possible structure that is of importance for modeling dynamic
systems is the cellular automaton, which has been studied extensively for half a century
On the other hand, to analyze a system governed by the notion of state transition,
logic programming can be a good tool to describe and model dynamic systems. As
shown by
In this paper, we will introduce a lifted correspondence based on the fact that
a cellular automaton can be viewed as a Boolean network with multiple cell states
and an in nite amount of nodes. We will map con gurations of a cellular
automaton to interpretations of the corresponding logic program, and will show as well
a translation to calculate one of these structures from the other. The cellular
automata structure in this paper is de ned as grid-based cellular automata, which
include Conway's Game of Life
There are a few works that apply logic programming to cellular automata in
the literature. A way to simulate a cellular automaton with a logic program has
been brought up by (Syrjanen 2000). However, their approach is to simulate a
cellular automaton with a logic program, so that some problems can be computed
using Answer Set Programming, rather than to regard a cellular automaton as a
logic program, which lends itself to di erent applications than our approach. A
similar simulation has been considered by
Normal logic programs have been regarded as cellular automata by
A cellular automaton consists of the following components
Cells are arranged on an in nite Cartesian grid.
The cells that determine a cell's successor state are in the neighborhood of
the cell. This neighborhood is de ned via a maximum distance with respect
to some norm on the Cartesian space.
From these two properties, we de ne a cellular automaton as follows
A d-dimensional unbounded cellular automaton (UCA) is a quadruple (Zd; Q; r; ), where
Zd is the cell space of the automaton, where Z is the set of integers.
Q is the set of states a cell can have.
r is the radius of a cell's neighborhood, which is a square of cells around the
original cell. We can calculate the area of the neighborhood as a := (2r+1)d. If
r = 1 and d = 2, this neighborhood is equivalent to the Moore neighborhood
: Qa ! Q is a local transition function that maps the current states of a cell's neighbors to the next state of that cell.
Furthermore, we de ne a function : Zd ! Q to be the con guration of the cellular automaton, assigning a state to each cell of the cell space. Finally, the transition function of the whole cellular automaton : (Zd ! Q) ! (Zd ! Q) is given by ( ( ))(c) = ( (c1); : : : ; (ca)), where c1; : : : ; ca are the neighbors of the cell c. A consecutive sequence of con gurations obtained by state transitions is called a trajectory (or an orbit) of the cellular automaton.
While this de nition allows us to de ne well-known cellular automata such as
Conway's Game of Life
A d-dimensional one-way bounded cellular automaton (OBCA) is a quadruple (Nd; Q; r; P ), where
Nd is the cell space of the automaton, where N is the set of natural numbers. Q is the set of states a cell can have. r is the radius of a cell's neighborhood. In contrast to an UCA, this neighborhood is not of the same size for all cells; cells that are close to the boundary of the cell space (i.e., at least one of the coordinates is smaller than the radius) have a smaller neighborhood. The area is given by ac := id=1(yi + r + 1); c = (x1; : : : ; xd); yi = min(r; xi).
P = f k j k 2 f0; : : : ; rgdg is a set of local transition functions. The transition function k(c) assigned to a cell c is given by k(c) = (min(r; c1); : : : ; min(r; cd)). As a shorthand, we write the function assigned to a cell c as c. This function has a signature of c : Qac ! Q Again, we de ne a function : Nd ! Q to be the con guration of the cellular automaton and give the transition function by ( ( ))(c) = c( (c1); : : : ; (cac )).
program (NLP) P is a set of rules of the form
A
A1 ^
^ Am ^ :Am+1 ^
^ :An
where A and Ai's are atoms (n m 0). For each rule R, we de ne that h(R) = A,
b+(R) = fA1; : : : ; Amg and b (R) = fAm+1; : : : ; Ang. A set of ground atoms is a
model of P, if for any rule R and any substitution of variables , b+(R) I and
b (R) \ I = ; imply that h(R) 2 I. A model I is a supported model if, for any
A 2 I, there exists a rule R 2 P and a substitution such that (i) A = h(R) , (ii)
b+(R) I, and (iii) b (R) \ I = ;. Furthermore, we use the TP -operator given
by
TP (I) =
h(R) j R 2 P; b+(R) 2 I; b (R) \ I = ; : From this de nition, it follows that I is a supported model i TP (I) = I.
Given a logic program P and an Herbrand interpretation I, the orbit of I with T k+1(I) = TP (TPP ko(pIe)r)atfoorr kis=th0e; 1s;e:q:u:e(nBcleaihrT,PDku(sIh)iink,2a!n,dwHheurmeeTnPn01(I9)97=). I and respect to the T
P
Given an OBCA A = (Nd; Q; r; P ), we want to construct an NLP with the semantics that a con guration of the OBCA corresponds to an Herbrand interpretation I of the NLP. The con guration 0 = ( ) corresponds to the set I0 = TP (I). To this end, we construct a logic program with the following structure:
A unary function symbol s=1 A set of predicates fpi=d j 1 i dlog2jQjeg The relation between the elements of the logic program's Herbrand base and the cell states of the automaton is as follows: A cell c = (x1; : : : ; xd) is encoded as the tuple (sx1 (0); : : : ; sxd (0)). (sx(0) denotes x applications of s to 0) This cell's state is encoded by the truth assignment of the predicates over this tuple in the given model. This encoding is done in a binary fashion, that is, we enumerate the states in Q as Q = q0; : : : ; qjQj 1 . We then choose predicates fpb1 ; : : : ; pbm g such that m X 2bi 1 = t; (c) = qt i=1 For example, if in a two-dimensional automaton with 6 states the cell c = (1; 2) has the state q5, we encode this in I as p1(s(0); s(s(0))) 2 I, p3(s(0); s(s(0))) 2 I and p2(s(0); s(s(0)) 2= I, since 5 = 20 + 22 implies that p1(c) and p3(c) are true while p2(c) is false.
We want to generate rules for the NLP from the local transition functions c according to the following algorithm. Let k := dlog2jQje. We can use a binary encoding (see above) to encode each qi 2 Q as an element of the Boolean product Bk. Using this encoding, we generate a set of functions 'c : Bk ac ! Bk. We can then split the resulting vector of Booleans into its k components and create k separate functions 'c;i : Bk ac ! B. These functions are classical propositional formulas; therefore, we can convert them to disjunctive normal form, i.e., where c;i;j only contains (possibly negated) literals and the conjunction operator. These c;i;j will form the basis for the logic program, and there will be exactly one rule for each c;i;j . In the following, (c; i) calculates the i-th cell of the cell c's neighborhood by some enumeration. This enumeration has to be equivalent to the one used for the ordering of the arguments of c;i;j . The rules have the following form: pi(#c;c;1(X1); : : : ; #c;c;d(Xd)) c;i;j (p1(#c; (c;1);1(X1); : : : ; #c; (c;1);d(Xd));
: : : pk(#c; (c;1);1(X1); : : : ; #c; (c;1);d(Xd)); p1(#c; (c;2);1(X1); : : : ; #c; (c;2);d(Xd));
: : :
pk(#c; (c;ac);1(X1); : : : ; #c; (c;ac);d(Xd)))
The functions # ensure that the correct amount of applications of the successor
function s are applied to the variables, or alternatively to the constant 0. They are
de ned as follows:
The next theorem can be proved in a similar way to
Let A be an OBCA, and any con guration of A. Let PA and I be an NLP and an Herbrand interpretation obtained from A and by the above translation, respectively. Then, there is a one-to-one correspondence between the trajectory of A starting from and the orbit of I with respect to PA.
Consider the one-dimensional OBCA A = (N; f0; 1; 2g ; 1; f 0; 1g), where 0(c; r) = r 1(l; c; r) = l + r (mod 3) p1(0) p1(s(0)) p1(0),p1(s2(0)) p2(s(0)),p1(s3(0)) p2(0),p1(s4 (0)) p2(s(0)),p1(s3(0)),p1(s5(0)) p2(0),p2(s4 (0)),p1(s6(0)) p2(s(0)),p2(s3(0)),p1(s7(0)) p2(0),p1(s2(0)),p2(s4(0)),p1(s6(0)),p1(s8(0)) 0;1;0(c1; c2; r1; r2) = r1 0;2;0(c1; c2; r1; r2) = r2 1;1;0(l1; l2; c1; c2; r1; r2) = l1 ^ :r1 ^ :r2 1;1;1(l1; l2; c1; c2; r1; r2) = r1 ^ :l1 ^ :l2 1;1;2(l1; l2; c1; c2; r1; r2) = l2 ^ r2 1;2;0(l1; l2; c1; c2; r1; r2) = l2 ^ :r1 ^ :r2 1;2;1(l1; l2; c1; c2; r1; r2) = r2 ^ :l1 ^ :l2 1;2;2(l1; l2; c1; c2; r1; r2) = l1 ^ r1 These functions are converted into rules of the logic program, exemplarily done for 0;1;0 and 1;2;2:
To obtain the construction for a UCA A = (Zd; Q; r; ) , we take the above construction and modify it to accomodate the bidirectionally in nite cellspace. One can view the cellspace Nd as one orthant of the d-dimensional space Zd. The basic idea of our construction is to view each orthant of Zd as a seperate OBCA with the same, albeit mirrored behaviour. We accordingly generate similar rules for each orthant, and a set of rules for the hyperplanes at which at least one coordinate is in a radius around zero, i.e. where the orthants touch. There are multiple ways one can extend our previous construction to accomodate this cellspace. We chose the following idea: Instead of using one successor function s, we use two functions, s+ and s . A cell c = (x1; : : : ; xd) is now encoded as the tuple with sgn de ned as: (sjsxg1nj(x1)(0); : : : ; sjsxgdnj(xd)(0)) sgn(x) = (+ x
0 x < 0 For example, the cell ( 2; 0; 3) is encoded as (s2 (0); 0; s3+(0)). The encoding of state using this cell encoding proceeds as with OBCAs, via a binary encoding using the predicates. To generate the rules, we reuse the concept from our OBCA construction. The key di erence is that a UCA only has a single transition function , but we have to generate multiple sets of rules depending on the orthant. To be speci c, there need to be (2r + 3)d rulesets. For example, take a two-dimensional UCA with r = 1. This UCA needs 25 rulesets, with the following 5 terms for both coordinates: s (s (X)) for general negative values, s (0) for 1, 0 for 0, s+(0) for 1, and s+(s+(X)) for general positive values.
Why we need to treat 1 and 1 seperately is easily shown with an example. Suppose we want a UCA in which every cell copies the cell to its left. If we just take s (X), 0 and s+(X) as terms, we will generate a rule p(s+(X); Y ) p(X; Y ). However, this rule would also re for p(s (0); 0), leading to a con guration with p(s+(s (0)); 0) in its Herbrand interpretation. This is a forbidden atom, since it has no corresponding cell.
To prevent such inconsistencies, we have to ensure function symbols cannot be mixed, and this is achieved by adding these extra rules, so that the aforementioned automaton would instead generate the rules p(s+(s+(X)); Y ) p(s+(X); Y ) and p(s+(0); Y ) p(0; Y ).
To generate the rulesets, we use the same structure as in the OBCA construction, but with the following adapted function #:
Consider the one-dimensional OBCA A = (Z; f0; 1g ; 1; ), where (l; c; r) = min(l; r) p1(s-4(0)),p1(s-2(0)),p1(0),p1(s+(0)),p1(s+2(0)),p1(s+4(0)) p1(s-3(0)),p1(s-(0)),p1(s+(0)),p1(s+3(0)) p1(s-2(0)),p1(0),p1(s+2(0)) p1(s-(0)),p1(s+(0)) p1(0)
As we have demonstrated, there are constructions for both OBCAs and UCAs that give an equivalent NLP. The converse, however, is not generally true. It is trivially easy to construct an NLP that has no corresponding cellular automaton, because it violates locality.
Consider the NLP p(0) p(X) Taken as a one-dimensional OBCA, the cell 0 is in uenced by an in nite number of cells, which cannot be represented as a nite neighborhood in a grid. To obtain a set of NLPs for which we can nd a corresponding cellular automaton, we have to place strong restrictions on the form of the NLPs. By doing this, we essentially obtain the set of NLPs that are generated by our construction from cellular automata, plus transformations that do not change the meaning of the NLP.
Essentially, the NLPs we can translate back to OBCAs have to use only predicates of the same arity, the terms in the heads can be only 0 to si(0) and si+1(Xj ), and the terms in the body have to be the terms in the head at the same position, with the only di erence being the application depth of s.
This is an LP that can be translated back to a CA p(s2(X1); s(0); 0)
p1(s3(X1); 0; s(0)); p2(s(X1); s2(0); 0)
Hence, to obtain cellular automata for a larger set of NLPs, one would have to
use a more general model of cellular automata, such as the one proposed by
Now that we have derived a construction between logic programs and cellular
automata, we are able to view problems from cellular automata theory as problems
of logic programming and, by extension, rst-order logic. We now show how some
computational problems can be translated to rst-order logic programs, and which
conclusions we can draw from this. Before we can examine these problems, we rst
give de nitions of well-known objects from cellular automata theory, as well as a
de nition of Turing machines that will be used in various proofs. Note that some
results about the decidability of in nite behavior of general (i.e., non-OB)
cellular automata have been found in
A still life is a con guration c of a cellular automaton which is a xpoint of the transition function , that is, a con guration ful lling (c) = c.
Note that a xpoint of translates to a xpoint of the TP operator, i.e., a supported
model of the logic program
An oscillator is a sequence of con gurations (c1; : : : ; cn) of a cellular automaton that form an attractor of the transition function , that is, they ful ll (ci) = ci+1 for i < n, and (cn) = c1.
The corresponding attractor of the TP forms a supported class of the logic program
A spaceship is an in nite sequence of con gurations (ci)i2N+ a period n 2 N+ and
a translation t 2 Nd of a cellular automaton with the following properties:
(ci) = ci+1
ci + t = ci+n
A classic example of a spaceship is the glider in Game of Life
There are many largely equivalent de nitions of a Turing machine. We will use the following de nition:
A one-way bounded Turing Machine (OBTM) consists of a quintuple (Q; ; q0; ; ), where Q is the set of states, is the tape alphabet, xed to = f0; 1; g, q0 is the initial state, is the blank tape symbol, and : Q ! Q f ; #; !g is the transition function. The tape of this Turing machine is bounded to the left and in nite to the right, much like the cell space of a one-dimensional OBCA. Furthermore, we de ne that the machine halts if a transition is taken where the direction of the head movement is #.
Since logic programs and Turing machines are both computationally universal, it is possible to encode one as the other. However, here it is important to guarantee that encoding of a Turing machine into an NLP can be done within the class of NLPs that can be translated to cellular automata.
The orbit problems we are considering have the form: Given an OBCA A and a con guration c, does the orbit of c contain a con guration that exhibits a property P ?
The orbit problem of still lives is undecidable.
Given an OBTM M, construct the corresponding logic program and from that the
corresponding OBCA. Observe that the head always moves, unless the OBTM halts.
The OBTM reaches a still life i it halts. Therefore, the orbit of a con guration c
leads to a still life i M halts on c. Therefore, if there was an algorithm to decide
the orbit problem of still lives, this algorithm could be used to decide the halting
problem, which is known to be undecidable
The question whether an orbit of the TP operator leads to a supported model is undecidable.
The orbit problem of spaceships is undecidable.
Given an OBTM M, construct an OBTM M0 that does the following:
Write a 1 to the now free rst cell; Simulate M on the moved input;
If M terminates, clear the tape and simulate any spaceship.
If M terminates, the orbit of the starting con guration on M0 leads into a spaceship. If M does not terminate, the rst cell of the tape never clears, which means that the whole con guration does not perform a translation, so there is no spaceship. Therefore, if there was an algorithm to decide the orbit problem of spaceships, this algorithm could be used to decide the halting problem.
Similar arguments can be made for oscillators or other orbit problems, therefore:
The question whether an orbit of the TP operator leads to an attractor is undecidable.
The other two problems are the testing problem (Given an OBCA A and a con guration c, does c exhibit a property P ? ) and the existence problem (Given an OBCA A, is there a con guration c that exhibits a property P ? ).
There is a variety of avenues in which research still is ongoing. First of all, one of the most restrictive conditions in the given construction lies in the translation from logic programs to cellular automata. Since only a limited class of logic programs is captured by that construction, we cannot readily use it to perform proofs or create models for general logic programs; therefore, we are interested in a more general class of cellular automata that is capable of modeling a wider range of logic programs. Since such a construction inevitably sacri ces the grid-based cellular automaton model as well as a notion of locality, it remains to be seen whether there is a general structure that retains some useful properties, or if the general automaton model is so unspeci c that it has no value over using the logic program directly. Another possible result of research in this area is obtaining an automaton model that is not general, but more powerful than the given OBCAs and UCAs, for instance with a tree-based structure to transcend the carthesian cell space.
Going in the other direction, while OBCAs are ideal to model this restricted class of logic programs, the classical notion of cellular automata (for instance, Conway's Game of Life) utilizes an unbounded grid, as described in the UCA structure. Problems in this area include the fact that the application depth of a function to a constant is a natural number, while the coordinates in a UCA are integers. Although there exist several bijections between the natural and integer sets, it is di cult to use one of these bijections properly, as we have to preserve the notion of locality, that is, whether an integer is positive or negative, its neighborhood (as modelled by di erent application depths in the NLP) has to be the same. Other approaches, such as using one function for positive and one for negative integers, have the problem that only a subset of all Herbrand interpretations translate to legal con gurations of the CA. Therefore, existence proofs on the logic program do not trivially correspond to existence proofs on the cellular automaton.