Atypical Output Rules

Atypical Output Rules - The connection between cellular automata and sorting algorithms

I mentioned briefly in section 1 that elementary cellular automata have a lot in common with sorting algorithms. Sorting algorithms have simple rules that check the values in an array, and if the algorithm tests a configuration that it has a rule for, it performs an operation. The tests a sorting algorithm performs are similar to the tests automata perform. In fact, I am going to make the argument that sorting algorithms are, in fact, automata. Sorting algorithms are like the the Imperfects class, but the operation the sorting algorithm performs is not a set, but a swap. What would happen if you incorporated a swap rule into an automaton rule? When we think of automata, we have a chauvinism toward set operations. But does an automata really have to only perform set operations? Who decided that? Again, it seems that people don't want to accept any creativity in automata ruleset design. This is unfortunate because there are probably a lot of really interesting automaton behaviors going undiscovered simply because people don't think it's allowed. Well, take this as permission to try some atypical operations (operations performed as a result of checking for some sequence of values). I think allowing for new kinds of output rules will demonstrate intriguing behavior.

Okay, if we allow for rules other than just set operations, what other kinds of operations might we perform? How about swap? If an automaton can perform a test on multiple inputs, maybe it could also perform multiple output operations. Maybe logic gates?

Let's consider some examples of possible output rules.

Set - Set the element to one of n possible values. This rule is currently used by all automata.

Swap - Swap the positions of two elements in the next timestep.

Not - Assuming the ruleset acts on binary inputs, do a bit flip of a specific element in the next timestep.

AND - Compute the Boolean AND of two or more input bits and output the result to the next timestep.

OR - Compute the Boolean OR of two or more input bits and output the result to the next timestep.

NAND - Compute the Boolean NAND of two or more input bits and output the result to the next timestep.

NOR - Compute the Boolean NOR of two or more input bits and output the result to the next timestep.

XOR - Compute the Boolean XOR of two or more input bits and output the result to the next timestep.

XNOR - Compute the Boolean XNOR of two or more input bits and output the result to the next timestep.

Duplicate - Duplicate the value of a cell at some index of the next timestep to the current index of the next timestep.

Cycle - Store a value at the start of the automata, as the rule is applied, increment or decrement the value and set it to some index of the next timestep.

Add - Add the values of two indices and set the output sum to the value of some index in the next timestep.

Subtract - Subtract the values of two indices and set the output to the value of some index in the next timestep.

Modulo - Compute the modulo of a cell (the remainder after a division) and set the output to some index in the next timestep.

Rules that interact with each other:

Copy - Copy the value of a cell at some index of the next timestep (there is no output to the next timestep).

Paste - Paste a previously copied value to some index of the next timestep (the value that was copied by a copy sequence).

Let’s assume for a second that no one has a problem with using different kinds of output rules other than set instructions. Look again at the 4-ruled automaton capable of complexity.

The r000 variable stores a 1 - The r001 variable stores a 1 - the r010 variable stores a 0 - the r1 variable stores a 1

The rules state to first check for a 011 such that X[i-1] = 0, X[i] = 1 and X[i+1] = 1, if you find those elements in that order, set the cell directly center below the three cells to a 1. If you do not find the first configuration, check if the order of cells X[i-1], X[i], and X[i+1] are 1,1, and 0, respectively. If you find that configuration, set the center cell below the current three cells to a 1. If you don’t find that configuration, tech for X[i] = 1 and X[i+1] = 0, if you find it, set the leftwise cell below to a 0. Finally you don’t find any of those configurations, chick if X[i] =0 and if X[i+1] = 0, if they are, set the leftwards cell in the next timestep to a 1.

This produces the complex automaton behavior above. Here is the list of rules simplified. Notice that the output positions are midwise for the first two rules (the imperfect 3-space rules) and leftwise for the last two rules (the imperfect 2-space rules).

Ruleset

Let’s now add an atypical output rule to the end of the if else(){} rules.

else if(X[i] == 0 && X[i+1]==1){

int first = X[i-1];

int next = X[i];

this.newX[i-1] = next;

this.newX[i] = first;

}

This is akin to how sorting algorithms function. It checks the positions of n-space elements in an array, and swaps their order. This is part of the ruleset for the Bubble Sort algorithm.

Will adding this rule to the end of the if else statements shown in the image above, change the behavior of the automaton (image at top of the page)? There's only one way to find out...

Below shows the output of the original 4-ruled automaton (Left) and the output of the automaton with a swap rule added to the end of the if else statements (Right).

The behavior of each automaton is clearly different, not very different, but that isn't what we were asking. We were asking if the behavior is at all different, and as you can see (and as you undoubtedly guessed) the behaviors are not the same. But of course they aren't! We changed the rules so we got a different result. The whole point I'm making here is to show that outputs of rules do not need to be set functions, they can be all kinds of functions.

Let's look again at rule 30.

Let's change one of the rules so that it performs a swap rather than a set as its output function.

Quickly, let me go over some pseudocode so we can accurately represent our algorithms.

A set function can be written like a method with two parameters. The first argument passed into the set() function is the value being set and the second argument is the position of the element in the next timestep. For example, if we wanted to rewrite the first if statement below in pseudocode, we could say:

if X[i-1] = 0 and X[i] = 0 and X[i+1] = 0:

set(0,i).

Note that the colon ':' denotes the end of the test, and the period '.' denotes the end of the entire code block.

Looking at the set() method in the pseudocode above: 0 is the value being set and i is the position in the next array you are setting the value to.

A swap function could be written as:

swap(i-1,i)

This means the value at position i-1 of the current timestep is copied to a variable a; the value at position i of the current timestep is copied to a variable b. In the next timestep, set the value at i-1 to b and set the value of i to a. This swaps the order of the two elements. Note that the order of the swap with only two parameters is arbitrary. swap(i-1,i) and swap(i,i-1) are identical instructions and would yield the same result.

What will be the result of changing rule 30 such that instead of performing a set(0,i) if the last if else rule below runs, it instead performs the following rule expressed in the pseudocode:

if X[i-1] = 1 and if X[i] = 1 and if X[i+1] = 1:

swap(i-1,i).

Look at the if else statements below. Look at the very last rule in the code block. What is expressed in the pseudocode above is what is being performed by the algorithm below.

Let's compare the output of the unedited rule 30 automaton to the rule 30 that performs:

if X[i-1] = 1 and if X[i] = 1 and if X[i+1] = 1:

swap(i-1,i).

On the left, below, is the unedited rule 30 and on the right, below, is rule 30 with the swap function denoted above.

Section 8