Arithmetical Cellular Automata

Johan Veerman

Pontificia Universidad Católica del Perú

Overview

We know that there are CA with universal computation capabilities, yet we do not know how to program them, that is, encode an input and decode the output. We therefore consider a bottom-up approach, by programming and searching for CA that have the ability to calculate mathematical functions. In order to gain some insight on how these arithmetical CA behave, we start constructing some rules that perform some simple arithmetical calculations, and then we use what we learn from their behavior to perform searches in CA rule space.

Specific Constructions

Serial Constructions

Parallel Constructions

Searches in CA Rule Space

Specific Constructions

Defining a calculation

There are many ways to encode an initial condition. For this work, we consider codification in unary and in the following format:

Input, Particle, Input

Let's look at an example of what we do not consider to be a calculation in this context:

This is the same CA, shown in TableForm and as an ArrayPlot. This CA is effectively adding both inputs, but it does not read both of them. For a certain calculation to be "legal" we will require that the moving particle reads both inputs.

Other requirements for the serial constructions:

Static Input Condition:	the input and the background do not interact and do not move.
Serial Condition:		there is only one moving particle at any time.
Halting Condition:		when the CA has reached an answer it must halt.

Specific Constructions - Serial

Subtraction

We can program a CA to serially subtract one quantity from another by making a particle read the input from one side and eliminate it from the other, as shown below:

The colors or states used for this construction are described below:

0:	background
1:	input (in unary)

s1:	a particle moving right through the background that reads and eliminates right input
s2:	a particle moving left through the background that eliminates left input
s3:	a particle that starts a wall
s4:	a wall

Specific Constructions - Serial

Addition

For the case of addition, we need the particle to carry the input from the right and "add it" (attach it) to the left:

In addition to the background (0) and the input (1), the CA uses the following states:

a1:	a particle moving right through the background that reads eliminates right input
a2:	a particle moving left through the background
a3:	a particle moving right through the left input
a4:	a particle moving left through the left input
a5:	a particle that adds to the output at the left and serves as a wall
a6:	a particle that signals when to start the wall

Addition uses more states for the moving particle because it has to pass through two different kinds of media.

Specific Constructions - Serial

Division

Only for exact divisions. Some sort of memory has to be build in the CA. The "memory" states are:

x1:	unused memory
x2:	used memory

Specific Constructions - Serial

Direct Multiplication

The same as before, only that the memory is now implemented at the left:

Specific Constructions - Serial

Embedded Multiplication

Let's now say that we want to multiply as a series of additions. First we need to generalize the addition CA so that it can add an arbitrary number of inputs:

As it is, the general addition CA will only add all the inputs if the moving particle is located between the two leftmost inputs. So now we need some kind of construct that -starting between any two inputs- will create a wall at the right to signal when the computation must stop and then move right to start the addition:

Specific Constructions - Serial

Embedded Multiplication (Cont.)

Combining both conctructions shown before along with some commands we now have a CA that multiplies two inputs as a series of embedded additions:

So now we have a CA that can do both addition and multiplication, depending on the particle at the initial condition.

Specific Constructions - Serial

Exponentiation

Finally, exponentiation can be constructed as before, either directly or as a series of embedded multiplications (which at the same time include a series of embedded additions). In both cases, a new level of "memory" states has to be included. Just as an example, this is the exponentiation CA with embedded multiplications:

Specific Constructions - Serial

Discussion

CA are highly parallel systems. Making them calculate serially makes them very innefficient.

Direct vs. embedded multiplication

An alternative: Multifunction CA. A single CA that, depending on the particle at the initial condition, does many arithmetical functions. Background and Input states are shared. Others are different according to function.

Three types of behavior account for all arithmetical functions:

Elimination + Elimination = Subtraction
Elimination + Creation = Addition
Elimination + Creation + Memory (right input) = Division
Elimination + Creation + Memory (left input) = Multiplication
Elimination + Creation + Memory (left input, 2 levels) = Exponentiation
Elimination + Creation + Memory (left input, 3 levels) = Tetration

Specific Constructions - Parallel

Subtraction

We now change the Serial Condition for the following:

Parallel Condition:	many particles. Information in one of the inputs is read only once.

So now, for the case of subtraction we will only need:

s1:	a particle moving right through the background and erasing right input
s2:	a particle moving left through the background and erasing left input

Specific Constructions - Parallel

Addition

For addition, we need the following:

a1:	a particle moving right through the background and erasing right input
a2:	a particle moving left through the background
a3:	a particle moving left through the left input and adding input at the left

Specific Constructions - Parallel

Embedded Multiplication

Again, we need to generalize the parallel addition CA for an arbitrary number of inputs, except that this time it has to perform the whole addition at the same time. A delay state must be introduced whenever crossing between particles happen:

a4:	a delay particle also used for overlapping states of a1 and a2 or a1 and a3

Specific Constructions - Parallel

Embedded Multiplication (Cont.)

With the above construction, we get a parallel multiplication CA with embedded addition:

Specific Constructions - Parallel

Discussion

Parallelism dramatically reduces the number of states and the number of steps to perform a certain computation. In some cases though, it can be much more harder to program.

The three types of behavior observed before also appear in the parallel constructions.

We are interested in the most efficient way to calculate an arithmetical function (number of steps), implemented in the simplest possible way (number of colors). These considerations are taken into account for the searches in the CA rule space.

Searches in CA Rule Space

The Method

We now because of the conditions imposed at the beginning,that the number of colors foranykind of computation has to be more than two (background and input).

CA rule spaces for three or more colors can be unmanageable for exhaustive searches. We therefore tried to devise a method to narrow down the rule space. The steps where the following:

1. First we fix the Static Input Condition, which is the same as rule 204 of the ECA.

2. At this point, any other initial assumptions about some bits of the rule are include. We call this "frozen bits".

3. We then make a random search in the reduced CA rule space of a certain number of rules (50, for example) that meet the following criteria: they give a desired result encoded in the same way as the initial condition and it has to halt.

4. After these rules are found, they are passed through some filters. Basically, they are tried out with many different initial conditions and results. To follow our example, let's say that from 50 randomly found rules only 10 pass these tests.

5. These rules are then compared, bit by bit, to see which of them are repeated in all -or most-of the rules. These bits of the rule are turned into frozen bits, thus reducing the CA rule space further.

6. Repeat steps 3 to 5 until the CA rule space is reduced enough for an exhaustive search.

Searches in CA Rule Space

Subtraction

We have specifically consructed a CA that performs subtraction with 4 colors. We searched in a rule space of 3 colors to see if we could find some results. The size of the rule space is (3^19)  =  1, 162' 261, 467

Searches in CA Rule Space

Addition

Now we search for addition CA in a 4 color rule space ((4^56)).

Searches in CA Rule Space

Discussion

Searches for multiplication have also been tried in a CA rule space with 5 colors, but the number of possible rules ((5^117)) makes the search unfeasible, unless some further restrictions are applied. One possibility, reverse search.

The arithmetical CA found are simpler (less colors) and more efficient (a few less steps) than the ones specifically constructed.

Inside the calculations of the subtracting CA, all 4 kinds of behavior can be noticed. We are interested in Class I and Class II.

Problems with the searching method:

1. Most of the time, all of the bits are frozen in the first run, and then no more are.
2. Size of the random search is arbitrary.
3. Number of tests is arbitrary.
4. Freezing bits only when they are present in all filtered rules or just the majority of them.

Extending the radius:

steps[r_] := 
      2 Ceiling[Length[input2]/r] + Floor[Length[input2]/r] + 1

Working Hypothesis: Given enough states, there always exists a CA that performs a certain mathematical (arithmetical) function in the minimum number of steps.

Charting arithmetical CA in rule space:

1. Rule space = discrete space with (k^(2  r + 1)) dimensions.

2. Distance between rules using taxicab metric (Manhattan distance) defined as:

g[(x1, y1), (x2, y2)] = Abs[x1 - x2] + Abs[y1 - y2]

3. Pair separation histograms

Further Work

The BIG problem: searching in huge CA rule spaces

Computer architectures

Working with other simple programs

Primitives behind the calculations

Comparison with natural systems

NKS 2006 Questions

Will the next core computer architecture be discovered by search?

What will happen if kids learn cellular automata before algebra?