A New Kind of Science: The NKS Forum > Pure NKS > Where are ALL the additive rules?
Author
Tommaso Bolognesi
ISTI-CNR (Nat. Research Council)
Pisa

Registered: Jan 2005
Posts: 15

Where are ALL the 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
Tommaso Bolognesi
ISTI-CNR (Nat. Research Council)
Pisa

Registered: Jan 2005
Posts: 15

clarification

Reading p.952 more carefully I realize that reasonable sum functions (+) used to support the additivity of CA rules must yield a commutative monoid. This rules out, for example, the naive u(+)v = u from my previous post.

P. 952 mentions that, for elementary CA's,
the only two inequivalent commutative monoids are Xor and Or.
I wrote a little program for finding the additive rules relative to these sum operations. They are:

(+) defined as 'Xor':
0, 60, 90, 102, 150, 170, 204, 240

(+) defined as 'Or':
0, 170, 204, 238, 240, 250, 252, 254, 255

There are then two possible definitions for (+) that yield a commutative monoid in which the identity element is 1 rather than 0:

(+) defined as '=='
150, 153, 165, 170, 195, 204, 240, 255

(+) defined as 'And'
0, 128, 136, 160, 170, 192, 204, 240, 255

As expected, all these 'new' additive rules are indeed not new, being covered by the symmetries of the previous groups of rules.

__________________
========================================================================
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

02-10-2005 03:48 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  web resources  |  contact us