Tommaso Bolognesi
ISTI-CNR (Nat. Research Council)
Pisa
Registered: Jan 2005
Posts: 15 |
Where are ALL the additive rules?
On additive rules
---------------------
At p. 952 of the NKS book one reads:
'Of the 256 elementary cellular automata 8 are additive:
(0, 60, 90, 102, 150, 170, 204, 240)'.
Additivity for a given rule is proved by showing that there exists some
'addition' operation (+) over the CA states (rows) such that
the step function for that rule distributes over addition,
so that the next step of the 'sum' is the 'sum' of the separately
computed next steps.
The table at p. 884 provides boolean expressions for the elementary CA rules.
The expressions for the 8 rules above are:
Rule 0: phi(x1, x2, x3) = 0.
Rule 60: phi(x1, x2, x3) = Xor(x1,x2).
Rule 90: phi(x1, x2, x3) = Xor(x1,x3).
Rule 102: phi(x1, x2, x3) = Xor(x2,x3).
Rule 150: phi(x1, x2, x3) = Xor(x1,x2,x3).
Rule 170: phi(x1, x2, x3) = x3.
Rule 204: phi(x1, x2, x3) = x2.
Rule 240: phi(x1, x2, x3) = x1.
One can use these expressions while looking for the 'addition' operation
(+) that supports the proof of additivity for some rule.
I have noticed that for all the above rules, Phi distributes over (+) defined as
u(+)v = Xor(u, v)
However, other rules not included in the list above turn out to be additive.
At p. 952, in the note on Generalized additivity, Rule 250 is mentioned:
the relevant (+) operation is defined as Max[u,v] (that is 'Or').
I then started looking for other additive rules.
Consider rules:
153, 165, 195, 255
where
Rule 153: phi(x1, x2, x3) = Xor(x2, not x3)
Rule 165: phi(x1, x2, x3) = Xor(x1, not x3)
Rule 195: phi(x1, x2, x3) = Xor(x1, not x2)
Rule 255: phi(x1, x2, x3) = 1.
For all these rules Phi distributes over (+) defined as
u(+)v = (u == v)
First question: is there any reason for regarding
rules (0, 60, 90, 102, 150, 170, 204, 240) as somehow 'more additive'
than 250, or 153, 165, 195, 255?
Second question: is there a list of ALL additive rules somewhere,
maybe including the relevant (+) operation for each?
I have noticed that the 12 additive rules
0, 60, 90, 102, 150, 170, 204, 240,
153, 165, 195, 255
are precisely those that satisfy a sort of 'recursive applicability' property.
By this I mean (see diagram below) that the value of cell A
depends on the values of cells C1, C2, C3 exactly in the same way as
it depends on cells B1, B2, B3:
C1 -- C2 -- C3
-- B1 B2 B3 --
-- -- A -- --
In other words, A = phi(B1, B2, B3) = phi(C1, C2, C3).
By iterating, it turns out that a cell in these automata can be
computed based on the values of three cells located precisely 2**n rows above,
for any desired n.
This fact allows one to shortcut dramatically the computation
of future states of the automaton.
In particular, for computing row 2**n, one needs only compute
successive rows with indices equal to successive powers of 2.
Cost grows like the logarithm of the distance. Quite cheap.
Another consequence of this fact is that for intial conditions
of bounded width, future states of the automaton at distance 2**n
will show 'bit activity' (bit flippings) only within three increasingly
separated regions (horizontal segments),
each as wide as the (active part of the)
initial condition.
This appears to be consistent with the nested nature of the behaviour of some of these rules.
P.S.
Other trivial cases of additive rules
are those with simple phi functions involving only
one argument out of three, like rules 170, 204, 240 above.
These are rules:
15, 51, 85
where
Rule 15: phi(x1, x2, x3) = not(x1)
Rule 51: phi(x1, x2, x3) = not(x2)
Rule 85: phi(x1, x2, x3) = not(x3)
For all these rules Phi distributes over (+) defined as
u(+)v = u
__________________
========================================================================
Tommaso Bolognesi
Formal Methods && Tools Lab.
CNR - ISTI - Pisa - Italy
e-mail: t.bolognesi@iei.pi.cnr.it
web: http://matrix.iei.pi.cnr.it/FMT/
Report this post to a moderator | IP: Logged
|
01-18-2005 01:11 PM
