Chaos Found

6-Ruled Automata

Imperfect Permutable Sub-cellular Automata

Section 4

Outputs

A final thing we could consider changing is the amount of cells that get updated by a single rule. Ordinarily, a single rule updates a single cell. This is also an arbitrary formulation and it is the key to creating simpler ECA capable of complexity. What if we allow for more than one cell to be updated by a rule? This is how we make it happen! We need to add this possibility to our ruleset definition. A given rule can be n-out meaning it can output or set n possible states. If a rule can set multiple states in the next array, for example, maybe it can set the states of 2 elements, we would say it is 2-out. We are used to rules being single-out (1-out) but there is no reason this must be the case.

Consider the ruleset below.

Figure 2.9

Figure 2.9a: Source: https://writings.stephenwolfram.com/2019/10/announcing-the-rule-30-prizes/ Author: Stephen Wolfram

Remeber that the order matters! Imperfect permutable rules should be applied before perfect permutables.

This set of if blocks says to check the the cell to the left, if it is 0, check the current cell, if it is 0, check the next cell, if it is 1, set the cell in the next timestep at index i-1 to 1, and set the element at index i in the next timestep to 1.

If the first set of conditions are not met, check if the previous element was a 1, if the current element is a 0 and the next element is a 1, set the element of the next timestep at index i-1 to 0, and the element in the next timestep at index i to a 1.

If those conditions are not met, check all 2-space perfect permutations. Note that these rules are leftwise. If the current element is a 0 and the next element is a 0, set the element at index i of the next timestep to a 0.

If the current and next elements are 0 and 0 respectively, set the element in the next timestep to 0.

If the current and next elements are 0 and 1 respectively, set the element in the next timestep to 1.

If the current and next elements are 1 and 0 respectively, set the element in the next timestep to 1.

And finally, if the current and next elements are 1 and 1 respectively, set the element in the next timestep to 0.

Simply put, these are the rules:

Ruleset Order

001->bit[i-1]=1, bit[i]=1

101-> bit[i-1]=0, bit[i]=1

00->bit[i]=0

01->bit[i]=1

10->bit[i]=1

11->bit[i]=0

As you can see, there are a total of six rules in this ruleset. four of which are computationally simpler that Rule30. It is an imperfect binary 3-space 2-out (leftwise/midwise), perfect 2-space single-out leftwise elementary cellular automata. That is a mouthful. I think I'll just call it a sub-elementary cellular automata, or maybe just 'SCA'.

If we compare this ruleset to Rule30, we see that it has fewer rules and four of those rules are computationally simpler than all eight rules of the Rule30 ruleset. If we say that a test instruction is computationally equivalent to a set instruction, Rule30 has three tests per rule, and one set per rule. Giving a total of 4*8 = 32 computations.

Lets compare the number of computations to the SCA that demonstrates complexity.

Figure 3: Illustrates the partial permutable 3-space ,binary, 2-out rules with the perfect permutable 2-space binary 1-out rules

With 2 rules that have 5 computations each and 4 rules with only 3. Therefore, the SCA has a total of 22 total computations. Even if you encoded the order in which you apply the rules as a rule in itself, at most, it would add only 6 computations to the ruleset, totalling 28 computations, a number still smaller than the 32 computations needed for Rule30. I don't see any reason to say that the order is a rule, but just in case that was a criticism, the SCA still has fewer rules and less complexity in the specific rules than those of Rule30. The rules themselves (at least most of them) are computationally simpler, and there are fewer of them. I think this ECA (SCA) and it's equivalencies must be the simplest elementary cellular automata capable of complexity (computational irreducibility). The next step in this journey is to try out some of the paths I have laid out. Who knows, maybe you will find an even simpler one!

The next step in the journey for this SCA is to prove or disprove Turing Completeness. It is unknown whether this SCA is capable of universal computation.

You can find the code for this SCA at the bottom of this webpage.

I have added a 5th section outlining my discovery of a 5-ruled cellular automaton that generates complexity. Find the link at the bottom of this section.

Figure 3a

Figure 3b

Figure 3c

Figure 3d: Illustrates the locations of solitons in the partial permutable 3-space ,binary, 2-out rules with the perfect permutable 2-space binary 1-out rules

Full Code

package com.flotow;import java.util.Scanner;import java.lang.Math.*;public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); String shape; int r000; int r001; int r010; int r011; int runs = 0; int[] in = new int[1002]; for(int i = 0; i < in.length; i++){ if(i == 500){ in[i] = 1; }else{ in[i] = 0; } } System.out.println("Enter number of iterations."); System.out.println("----------------------------------"); int cycles = scan.nextInt(); int nums = 0; System.out.println("Choose the rule set. For the following cases\nEnter 1 if the rule should output a 1\nor Enter 0 if it should output 0."); System.out.println("00 -> "); r000 = scan.nextInt(); System.out.println("01 -> "); r001 = scan.nextInt(); System.out.println("10 -> "); r010 = scan.nextInt(); System.out.println("11 -> "); r011 = scan.nextInt(); System.out.println(""); System.out.println("What shape would you like to draw the fractal with?"); System.out.println(""); String wait = scan.nextLine(); shape = wait; String wait2 = scan.nextLine(); shape = wait2; System.out.println("Starting..."); System.out.println("----------------------------------"); while (true) { while (nums < cycles) { if(runs == 0) { Automata a = new Automata(in,r000,r001,r010,r011,shape); nums++; in = a.arrayOut(); } if(runs>0){ if(runs == 1){ RandomizeArray r = new RandomizeArray(); in = r.out(); } Automata b = new Automata(in,r000,r001,r010,r011,shape); in = b.arrayOut(); nums++; runs = 2; } } runs = 1; System.out.println("Go Again? ENTER 1 for yes or 0 for no."); int again = scan.nextInt(); if(again != 1){ break; } System.out.println("Enter number of iterations:"); System.out.println("----------------------------------"); cycles = scan.nextInt(); nums = 0; System.out.println("Choose the rule set. For the following cases\nEnter 1 if the rule should output a 1\nor Enter 0 if it should output 0."); System.out.println("00 -> "); r000 = scan.nextInt(); System.out.println("01 -> "); r001 = scan.nextInt(); System.out.println("10 -> "); r010 = scan.nextInt(); System.out.println("11 -> "); r011 = scan.nextInt(); System.out.println(""); System.out.println("What shape would you like to draw the fractal with?"); System.out.println(""); wait = scan.nextLine(); wait2 = scan.nextLine(); shape = wait2; System.out.println("Starting..."); System.out.println("----------------------------------"); } }}class Automata{ int[] X = new int[1002]; int[] newX = new int[1002]; int r000; int r001; int r010; int r011;
public Automata(int[] X, int r000, int r001, int r010, int r011, String shape) { this.r000 = r000; this.r001 = r001; this.r010 = r010; this.r011 = r011;
this.X = this.newX; CountCharacter c = new CountCharacter(shape); int spaces = c.stringCountOut(); String totalSpaces = ""; for(int s = 0; s < spaces; s++){ totalSpaces = totalSpaces+" "; } for(int j = 0; j < X.length-1; j++){ if(X[j]==0){ System.out.print(totalSpaces); }else{ System.out.print(shape); } } for (int i = 0; i < X.length-1; i++) { if (i == 0) { if(X[1000] == 0 && X[i] ==0 && X[i+1]==1){ this.newX[1000] = 1; this.newX[i] = 1; }else if(X[1000] == 1 && X[i] ==0 && X[i+1]==1){ this.newX[1000] = 0; this.newX[i] = 1; } else if ((X[i] == 0 && X[i + 1] == 0)) { this.newX[i] = this.r000; } else if ((X[i] == 0 && X[i + 1] == 1)) { this.newX[i] = this.r001; } else if ((X[i] == 1 && X[i + 1] == 0)) { this.newX[i] = this.r010; } else if ((X[i] == 1 && X[i + 1] == 1)) { this.newX[i] = this.r011; } } else if (i >= 1 && i <= 998) { if(X[i-1] == 0 && X[i] ==0 && X[i+1]==1){ this.newX[i-1] = 1; this.newX[i] = 1; }else if(X[i-1] == 1 && X[i] ==0 && X[i+1]==1){ this.newX[i-1] = 0; this.newX[i] = 1; }else if ((X[i] == 0 && X[i + 1] == 0)) { this.newX[i] = this.r000; } else if ((X[i] == 0 && X[i + 1] == 1)) { this.newX[i] = this.r001; } else if ((X[i] == 1 && X[i + 1] == 0)) { this.newX[i] = this.r010; } else if ((X[i] == 1 && X[i + 1] == 1)) { this.newX[i] = this.r011; } } else if (i == 999) { if(X[i-1] == 0 && X[i] ==0 && X[i+1]==1){ this.newX[i-1] = 1; this.newX[i] = 1;
} else if(X[i-1] == 1 && X[i] ==0 && X[i+1]==1){ this.newX[i-1] = 0; this.newX[i] = 1;
}else if ((X[i] == 0 && X[0] == 0)) { this.newX[i] = this.r000; }else if ((X[i] == 0 && X[0] == 1)) { this.newX[i] = this.r001; }else if ((X[i] == 1 && X[0] == 0)) { this.newX[i] = this.r010+1; }else if ((X[i] == 1 && X[0] == 1)) { this.newX[i] = this.r011; } } } for(int k = 0; k < X.length-1; k++){ this.X[k] = this.newX[k]; } System.out.println(""); } public int[] arrayOut(){ return this.X; }}class RandomizeArray{ int[] rando = new int[1002]; double randomNum = 0; public RandomizeArray(){ for(int i = 0; i < 1002; i++){ randomNum = Math.random(); if(i==500){ rando[i] = 1; }else{ rando[i] = 0; } } } public int[] out(){ return this.rando; }}
class CountCharacter { String in; int count; public CountCharacter(String in) { this.count = 0; for (int i = 0; i < in.length(); i++) { this.count++; } } public int stringCountOut(){ return this.count; }}

---------------------------------------------------------------------------------------------------------------------------------

After writing this site, I continued doing experiments on partial permutable Elementary Cellular Automata. My next set of experiments pertain not to partial permutables, but true partial rulesets. In section 5, I will show you an amazing cellular automaton I discovered that seems to generate complexity and it has ONLY 5 Rules! Check out my experiments in the next section.

Section 5