4-ruled Automaton that generates complexity

Chaos Found in 4-rules

Section 6

I can't believe how far this road goes... Here we are with 4-rules and still, complexity can arise. This SCA is partial in 3-space and partial in 2-space.

The ruleset for this partial automaton is...

011->1

110->1

10->0

00->1

This automaton has a striking similarity to the elementary CA rule 45: http://atlas.wolfram.com/01/01/45/

With everything I am learning about SCA, I am inclined to think there may be a 3-ruled automata that generates computationally irreducible behavior. We have seen a lot of interesting behavior so far. Let's look at the rest of the outputs this ruleset generates, next we will try some other related rules and catalogue what happens. After the code below, I have added images of all the outputs of this ruleset with all input permutations.

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 r1; 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("011 -> "); r000 = scan.nextInt(); System.out.println("110 -> "); r001 = scan.nextInt(); System.out.println("10 -> "); r010 = scan.nextInt(); System.out.println("00 -> "); r1 = 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,1,r1,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,1,r1,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("011 -> "); r000 = scan.nextInt(); System.out.println("110 -> "); r001 = scan.nextInt(); System.out.println("10 -> "); r010 = scan.nextInt(); System.out.println("00 -> "); r1 = 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; int r1; public Automata(int[] X, int r000, int r001, int r010, int r011,int r1, String shape) { this.r000 = r000; this.r001 = r001; this.r010 = r010; this.r011 = r011; this.r1 = r1;
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[i] == 1 && X[i + 1] == 1 && X[1000] ==0)) { this.newX[i] = this.r000; } else if ((X[i] == 1 && X[i + 1] == 0 && X[1000] == 1)) { this.newX[i] = this.r001;; } else if ((X[i] == 1 && X[i + 1] == 0)) { this.newX[i] = this.r010; }else if ((X[i] == 0 && X[i+1]==0)) { this.newX[i] = this.r1; } } else if (i >= 1 && i <= 998) { if ((X[i] == 1 && X[i + 1] == 1 && X[i-1] ==0)) { this.newX[i] = this.r000; } else if ((X[i] == 1 && X[i + 1] == 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] == 0 && X[i+1]==0)) { this.newX[i] = this.r1; } } else if (i == 999) { if ((X[i] == 1 && X[i + 1] == 1 && X[i-1] ==0)) { this.newX[i] = this.r000; }else if ((X[i] == 1 && X[i + 1] == 0 && X[i-1] == 1)) { this.newX[i] = this.r001; }else if ((X[i] == 1 && X[0] == 0)) { this.newX[i] = this.r010+1; }else if ((X[i] == 0 && X[i+1]==0)) { this.newX[i] = this.r1; } } } 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==600){ 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; }}

Let's take a look at some of the other patterns this ruleset generates.

011->0, 110->0, 10->0, 00->0

011->0, 110->0, 10->0, 00->1

011->0, 110->0, 10->1, 00->0

011->0, 110->0, 10->1, 00->1

011->0, 110->1, 10->0, 00->0

011->0, 110->1, 10->0, 00->1

011->0, 110->1, 10->1, 00->0

011->0, 110->1, 10->1, 00->1

011->1, 110->0, 10->0, 00->0

011->1, 110->0, 10->0, 00->1

011->1, 110->0, 10->1, 00->0

011->1, 110->0, 10->1, 00->1

011->1, 110->1, 10->0, 00->0

011->1, 110->1, 10->0, 00->1

011->1, 110->1, 10->1, 00->1

I would like to take this moment to point something out to the reader. I want to draw your attention to the shear immensity of possible rules one could consider exploring when coming up with rulesets that contain two (or more) partials. Let's think about this particular type of rule set outline above. What are the total possible experiments you would need to run to explore all possible permutations of the ruleset containing two 3-space, binary single-out and two 2-space binary single-out, rules, without repeating a ruleset? Holy crap...

If there are two 3-space positions to check, ____ ____ and each are capable of being 000, 001, 010, 011, 100, 101, 110, 111 (but not two of the same, for example, two rules can be identical - one rule can't be to check 000 and have a second rule also check 000 [or maybe we can, but let's save that possibility for later...]) and we can set the output to be either 0, or 1 (because it is binary) for each, AND we want to test all combinations of two 2-space positions, ____ ____ and each are capable of being 00, 01, 10, 11 and we can set the output for each of these to be either 0, or 1, there are already nearly 1000 possible combinations of two 2-space binary and two 3-space binary inputs and outputs. We know that order matters only when you have a perfect permutable, but since each each of these n-spaces are only partial, you can quadruple that number! There will be overlap though, for example, the current ruleset above can be run out of order because each test is so dissimilar from each other test that running it in any arbitrary order will produce the same behavior, but I'll come back to this. Since both the two 2-space and two 3-space are partial, we can run them in any order, each order will produce different behavior (assuming the tests have overlap). Even still, the immensity of possible rules is staggering and this is all with just 4 rules! It is safe to say that there is a lot of rich behavior out there in the partials. Who knows what all is out there!

Let me take a moment to prove that the order with which you apply the rules produces different output behaviors assuming at least two rules have overlap. Let's consider the ruleset: 00->0, 01->0, 010->1, 001->1

Look closely at the rules. Do you see why the order with which rules run is important? 00->0, 01->0, 010->1, 001->1 How about now? The rule 00 has the same initial bits being tested that the rule 001 does and the same is true for 01 and 010. Imagine a simple array:

0010101

In the first rule ordering, 00 runs first and so the value under the first 0 in the array will have a 0 generated under it in the next timestep. Now imagine instead that the ruleset was run such that the first test was 001. You see that in this case, the first 0 would have a 1 generated under it in the next timestep. In the universe of partials, the order with which rules are applied matters! The more rules in a given ruleset there are, the more the order with which those rules are applied becomes more and more important to the what the overall behavior of a CA.

In the next section, we are going to challenge the idea that the output of a given rule (the set instruction) is the only allowed instruction. In fact, one can come up with a whole host of different output instructions that change the behaviors of CA.

Section 7