Switch1329

[137ben]

I have been looking for methods to generalize 1d rules into 2 dimensions in a way such that the class 3 and class 4 properties of the 1d rule is preserved.
My initial idea was that the 1d rule could be applied to both the {w,c,e} sub-neighborhood and the {n,c,s} sub-neighborhood, and then the results would be added together mod k (for a k-state rule) to obtain the new value of cell c. However, this does not guarantee that the analog of a class 4 rule will necessarily be class 4.
As an example, here is the rule generated by applying this method to rule 110:

Code: Select all

# C,N,E,S,W,C'
n_states:2
neighborhood:vonNeumann
symmetries:none
0,0,0,0,0,0
0,0,0,0,1,0
0,0,0,1,0,1
0,0,0,1,1,1
0,0,1,0,0,1
0,0,1,0,1,1
0,0,1,1,0,0
0,0,1,1,1,0
0,1,0,0,0,0
0,1,0,0,1,0
0,1,0,1,0,1
0,1,0,1,1,1
0,1,1,0,0,1
0,1,1,0,1,1
0,1,1,1,0,0
0,1,1,1,1,0
1,0,0,0,0,0
1,0,0,0,1,0
1,0,0,1,0,0
1,0,0,1,1,0
1,0,1,0,0,0
1,0,1,0,1,1
1,0,1,1,0,0
1,0,1,1,1,1
1,1,0,0,0,0
1,1,0,0,1,0
1,1,0,1,0,1
1,1,0,1,1,1
1,1,1,0,0,0
1,1,1,0,1,1
1,1,1,1,0,1
1,1,1,1,1,0

It can easily be verified that this rule has none of the interesting properties of W110, and that the behavior it produces is extremely simple.

My next idea was that each cell would have two components: a "horizontal" component and a "vertical" component. From now on, I will denote the state of a cell either by {hor,ver}, or as an integer obtained by interpreting the string hor ver as a base-k integer (where k is the number of states in the 1d rule). So for a k-state 1d rule, the corresponding 2d rule would have k^2 states. At each step, the horizontal and vertical components would update independently. For example, if the 1d rule is W110, and the neighborhood of a cell is

Code: Select all

x0x
122
x3x

Then the next state of the center cell would be {w110(0,1,1),w110(0,0,1)}={1,1}=3.
However, this means that the horizontal and vertical components will never interact. Thus, the rule effectively runs an infinite number of parallel 1d universes. In other words, we have gained some extra states and a second dimension, but have not gained anything in the way of complexity.

The next method I thought of only works for 1d rules with 3 states. It is a variation on the previous method. Each cell has a horizontal and vertical component, as above. The step function works in 2 stages:
The first stage, called the pre-step, is identical to that in the previous method. The second stage interchanges state 5 ({1,2}) and state 7 ({2,1}).
For example, consider the 1d 3-state totalistic rule 1329. For the neighborhood

Code: Select all

x5x
836
x7x

the pre-step maps the center cell to {s1329(1,2,2),s1329(0,2,1)}={2,1}=7. The step function would therefore indicate that the center cell should be changed to a 5.
Note that both stages of the step function happen in a single.
The results of applying this method to totalistic rule 1329 is that the resulting rule (called switch1329) contains all of the patterns from the 1d rule (see Wolfram's A New Kind Of Science, pg. 287-289 for examples, including oscillators, spaceships, puffers, and spacefillers), but horizontal patterns can interact with vertical patterns in nontrivial ways.

There are many ways this can be generalized to 1d rules with more than 3 states. One possibility is to say that the horizontal and vertical components of each cell are exchanged EXCEPT when either component is 0. For a 1d rule with 4 states, this means that states the second stage of the 2d rule exchanges states 6 and 9, states 7 and 13, and states 11 and 14. Alternatively, we could assign several states as "stable" (i.e. is not exchanged between horizontal and vertical). The possibilities increase quite rapidly with the number of states. However, a 1d rule with 4 states already produces a 2d rule with 16 states. And since I am usually more interested in CA with simpler rules, I am mostly concerned with the 2d analogs of 3-color totalistic rules.

So, what can happen in, for example, switch1329? This is a 9-color rule in a JvN neighborhood, and it is class 4. Unfortunately, I am not sure of an efficient way to build a rule table. I did, however, make a Mathematica notebook for switch1329:

Code: Select all

s1329[0] := 0; s1329[1] := 2; s1329[2] := 0; s1329[3] := 1; 
s1329[4] := 1; s1329[5] := 2; s1329[6] := 1

hor[c_, n_, e_, s_, w_] := 
 s1329[IntegerDigits[c, 3, 2][[1]] + IntegerDigits[e, 3, 2][[1]] + 
   IntegerDigits[w, 3, 2][[1]]]

ver[c_, n_, e_, s_, w_] := 
 s1329[IntegerDigits[c, 3, 2][[2]] + IntegerDigits[n, 3, 2][[2]] + 
   IntegerDigits[s, 3, 2][[2]]]

pstep[c_, n_, e_, s_, w_] := 
 FromDigits[{hor[c, n, e, s, w], ver[c, n, e, s, w]}, 3]

step[c_, n_, e_, s_, w_] := 
 If[pstep[c, n, e, s, w] == 5, 7, 
  If[pstep[c, n, e, s, w] == 7, 5, pstep[c, n, e, s, w]]]

That gives the step function, which is compatible with the CellularAutomaton command. For example, a random array run for 100 steps can be given by

Code: Select all

ArrayPlot[
 Flatten[CellularAutomaton[{{{_, n_, _}, {w_, c_, e_}, {_, s_, _}} :> 
     step[c, n, e, s, w]}, {Table[
     Table[RandomInteger[{0, 8}], {i, 0, 5}], {j, 0, 5}], 
    0}, {{102}}], 1], ColorFunction -> "GrayTones"]

Here are some general things I have noticed from running random patterns, as well as from running collisions between a horizontal-glider and a vertical-glider:
--Most small patterns seem stabilize, though they take substantially longer to do so than in B3/S23
--A wide range of 1d oscillators occur naturally
--Occasionally, the horizontal components will die off completely, and all that survives are vertical oscillators and spaceships (or the vertical components die off, and only horizontal patterns remain). However, this is considerably rare; most of the time some horizontal oscillators and some vertical oscillators survive.
--It seems most natural objects are 1 dimensional. I'd expect that some nontrivial 2d objects exist, but that they are much rarer. Still, interactions between "horizontal objects" and "vertical objects" can occur, so it is theoretically possible to build complex 2d constructions which are impossible in one dimension.

Unfortunately, there are a number of disadvantages to using mathematica for this. Mathematica's ability to process computational systems is optimized to be useful for sampling a huge range of rules, in many different formats. It falls short, however, in searching for interesting patterns in a single 2d CA. For one thing, the dynamic updating (displaying each step as it is calculated) is very slow. It also can't use hashing the way Golly can. It is also significantly harder to share interesting patterns with people who don't have mathematica. I tried getting mathematica to generate a rule table from the step function, but I had trouble getting it into the correct format to copy/paste into notepad. And manually editing the format is out of the question, since the table would have 9^5 lines if no patterns are exploited. I'd expect there are several methods to shorten the rule table, though. Come to think of it, it might also be easier to generate a rule tree...though I don't know how rule trees work yet...guess I'll have to learn.

EDIT: *facepalm*! Just saw that if no variables are used and there are fewer than 10 states, then no commas are necessary for a rule table. That makes things a lot easier.
EDIT2: I can get it to appear in the correct format inside the mathematica window, but when I copy it into notepad, it adds { brakets around each line, and a comma between each line, making it unreadable to golly. Help?