Pre-Introduction

Let me start off by saying that the rulesets we will explore do not represent what we traditionally think of as cellular automata. These rulesets simply behave in a way that parallels the behavior of automata. I will add to this by saying, I believe the systems I describe on this site are just as legitimate as any other traditional automata ruleset, I just want to make sure it is clear to the reader that the systems I describe are Not cellular automata in the traditional sense. However, these systems do have a lot in common with cellular automata. I made this site to share my research and discoveries with you, the reader. This site uses non-standard terminology, but I did this to accurately describe the systems I have found and as a way to classify the hierarchy of simple programs I study. Note that definitions such as 'n-space', 'permutable', 'partial', 'nwise', and the like, are used to describe new kinds of systems that demonstrate interesting and even complex behavior, but are not the traditional vernacular in the study of simple programs. As I discover new phenomena, I immediately post my results so it is entirely possible that there are mistakes, but the systems I explore are real and I have made my code public so you, the reader, can see the results for yourself. Please take what you read with a grain of salt. My hope is that the information contained on this site will inspire you to study rulesets that are different than the norm. But, that's what science is. Science is about pushing the boundaries and seeing what's on the other side. I have found some pretty exciting and unusual rulesets and I hope that you will explore creatively designed, atypical rules for yourself. This is an exploration of the 'simplest' rules that generate exciting, peculiar and chaotic behavior. I consider different approaches for defining the complexity of a ruleset so as to categorize and compare them. This is a search for the simplest rulesets capable of complex behavior. Join me in this exploration into the profound and exciting world of 'sub-automata', or whatever you want to call them...

Without further ado, let's get to the crux of why I am so excited about atypical rules.

Simply put, an entire ecosystem of elementary cellular automata-esk systems exist that have yet to be explored. My original reason for creating this site was to just share these discoveries with others, but I have found that this ecosystem of automata is too vast for one person to adequately explore. This site will undergo changes in the coming weeks, but suffice it to say that there are numerous classes of automata that have gone unexplored, simply because no one has thought to try the atypical rules I outline on this site. The main discoveries I have made so far is that there are cellular automata with fewer and simpler rules than rule 30 that are capable of complex behavior. Now, it can be argued what constitutes 'simpler', and my approach is to literally count the total computations performed by a given ruleset in the worst case scenario - the runtime complexity of the algorithm. Maybe you have a better way to categorize rules by their complexity - I would love to hear what you think! There is a contact section at the top of this site. Please feel free to email me with any ideas or suggestions you may have. I will be adding a section to this site to allow for you to post new rules you discover so that we can explore this new landscape together. As I said, there is too much to explore for a single person. If you do decide to contribute new rules, even if those rules don't produce exciting behavior, simply exploring and posting your results helps all of us to better understand this new ecosystem. I started with a simple question, are there automata that are simpler than rule 30 that are capable of just as much complexity? The answer appears to be a resounding, yes! I classify automata by their rulesets and the main classes are (non-traditional terminology ahead) Perfect Permutable - these are the CAs that have an instruction for every possible permutation of cells for a given space. For example, the cellular automata you are likely familiar with are the perfect permutables like the ruleset below. Notice that every combination of 3-space permutations exist in this ruleset. 000, 001, 010, 011, 100, 101, 110, and 111. There are an infinite number of this type of CA. You can imagine a perfect permutable in 2-space: 00, 01, 10, and 11. 4-space: 0000, 0001, 0010, ..., 1101, 1110, 1111 - you get the idea.

The second class is the Imperfect Permutable rulesets. These rules are defined as rules that are perfect in some integer space but imperfect in some other integer space. For example, you may have a ruleset that tests only 2 of the 3-space rules, for example, 000 and 101, as well as a perfect permutable ruleset, for example 00, 01, 10, 11. Combined, they lead to some startling and exciting behavior which is outlined in this paper. There is an uncountably infinite set of imperfect permutable rulesets. The rules for the imperfect permutable ruleset I just described has some output for the following tests: 000, 101, 00, 01, 10, 11. This ruleset is imperfect in 3-space and perfect in 2-space.

The last class of rulesets I will outline here are the Imperfects. Where an Imperfect Permutable is imperfect in some integer space but perfect in another, the Imperfects are imperfect in all n-spaces. They do not have rules for all possible permutations of a given integer space. Allowing for these types of automata adds great richness to the kinds of systems one can design and test. As I have said, this has allowed me to discover a ruleset with only 4 rules that produces complexity like that of rule 30 in the perfect permutable 3-space class. If you want to see this ruleset, navigate to section 6. Throughout this paper I touch on many possible areas worth exploring. I hope you decide to try these out for yourself and even create and catalogue some rules of your own.

Introduction

My goal in sharing my findings is to show students and fellow computer scientists that complex behavior can be achieved with fewer, simpler rules than what describe Rule 30. If you want to skip ahead to the analysis of this CA with only 6 rules and the code that produces it, you can jump ahead to Section 4. However, in order to adequately analyze and define this CA, you should read all sections of material. The background knowledge herein will be extremely useful! If you want to see an automata-like ruleset that generates complexity with only 4 rules, skip ahead to section 6. Section 1 was written before I discovered 5 and 4-ruled cellular automaton capable of complexity. In this passage I reference that a 6-ruled automaton may be the simplest, but I have since discovered a CA that generates complexity with only 4 rules. See section 6 for the code to the simplest system capable of complexity that I discovered. Please note that this site is a work in progress and is updated as I find new phenomena in automata theory. All of my findings I have made since December 10th, 2020. This site will continue to be updated as more phenomena is found.

My second goal is to demonstrate other atypical rulesets with startling behavior can be formulated. Below is an image of an automaton I discovered while exploring various, atypical rulesets. I rigorously define the classes of rules that can be constructed to generate cellular automata and demonstrate computational irreducibility in systems of cellular automata that are simpler than elementary cellular automata such as rule 30. The image below is an automaton with rules 'simpler' than Rule 30. 'Simpler' is arguable, but it does appear to be the case. Another thing to note about this CA, it may even be Turing Complete (capable of Universal Computation).

"The basic feature a CA needs to perform computations is the capacity of its transition rule of producing “particle-like persistent propagating patterns” (Ilachinski 2001: 89), that is, localized, stable, but non-periodic configurations of groups of cells, sometimes called solitons in the literature, that can preserve their shape. These configurations can be seen as encoding packets of information, preserving them through time, and moving them from one place to another: information can propagate in time and space without undergoing important decay." - Stanford

The automaton below shows clear evidence of information propagation through time and space. Time can be thought of as the y-axis (from top to bottom) and space is x-axis (horizontal rows of cells). Now, appearing to transmit information through time and space does not necessarily mean it is capable of universal computation. It simply means that transmission of information is at least possible given some initial configurations of the starting array. To 'program' an elementary cellular automata, you must set the states of the initial array (1 or 0 for each cell - assuming it's binary) and the computation on those inputs occur as the cellular automata updates through timesteps. Every horizontal row is generated by the horizontal row above it (from the previous timestep). If it is capable of universal computation (that is, if it is Turing Complete) there is some configuration of on and off cells in a starting array that can compute any computable function.

Solitons can be seen on the left side of the image below. Therefore, it is at least possible that this elementary cellular automata could be capable of universal computation. One way this could be proved is if an arrangement of starting cells is discovered that act as logical NAND. NAND gates are universal logic gates which means NAND gates can be arranged into configurations that emulate all logic gates. If a NAND can be constructed, any computation can be computed by the cellular automaton below.

Even if it is found to not be Turing Complete, it is still a very simple automaton capable of complex and peculiar behavior worth exploration.

Solitons are identified between like-colored lines.

Although I call the cellular automaton (image above) elementary, that is not a technically precise term. Although I will refer to the following rulesets as elementary cellular automata, a more precise name would be sub-elementary cellular automata (SCA) or just subautomata.

Terminology

This site is an attempt to demonstrate that elementary cellular automata are not the simplest ruleset capable of complexity. I have discovered rulesets that can also achieve complexity (complexity here, means computational irreducibility - no equation exists that allows you to 'jump ahead' to know what the system will do, instead, one must perform the computation to know what will happen in a given system). Elementary cellular automata are systems of rules such that the cells in a given array each store one of two possible values - 0 (off state) or 1 (on state) - and depending on the values of neighboring cells, one can compute the values of cells for the next row (timestep t+1). After applying a particular ruleset to an array, the timestep increments by one, generating a row of cells directly below the previous row. The overall behavior of a particular ruleset is entirely dependent on the initial conditions of the starting array (which starting cells are on and which are off).

Below is an example of one such ruleset. The following elementary cellular automata (henceforth ECA) are what I call 3-space, binary, midwise rulesets. The integer value of n in n-space is determined by the states of how many cells must be 'checked' to determine the cell state of the next timestep. For example, take the famous ECA Rule 30. Rule 30 is a cellular automaton which demonstrates that simple rulesets can lead to complex, computationally irreducible interactions. Rule 30 is 3-space because, in order to determine the value of the cell in the next timestep, one must check the values of cells R30t-1[n-1], R30t-1[n] and R30t-1[n+1] (A total of 3 spaces must be checked). R30 stands for Rule 30, t stands for timestep, and [n] refers to the index of an element in the array R30. Let's look at the specific Ruleset for Rule 30.

This behavior was indeed surprising as conventional wisdom would lead you to think that simple rules necessitate simple behaviors. As you can see, that wisdom is completely wrong.

The ruleset above contains all possible permutations of 3-space binary states. Binary, in this context, refers to the number of states a given cell can take. In the case of rule 30, it has binary states 0 or 1 that a cell can be in. If there were 3 possible states, we would say it is a 3-space, ternary, midwise ruleset (I will define the rest of the terms in that description momentarily). Rulesets such as rule 30 are what I call 'perfect permutable' rulesets. This means there is a rule for every n-space permutation of possible states. (000, 001, 010, 011, 100, 101, 110, 111). If it were 3-space, ternary instead of 3-space binary, the rulesets would be (000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 212, 220, 221, 222). Each 3-space ternary rule could output a 0, 1 or a 2. If it were 4-space binary, your rules would look like the following (0000, 0001, 0010, 0011, ... 1110, 1111). 4-space quaternary would look like (0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, ... 3331, 3332, 3333). The total number of rules in a 4-space, quaternary, perfect-permutable ECA is 4^4 (four possible states [0, 1, 2, and 3] raised to the four possible positions [4-space]) which is a whopping 256 permutations. So instead of only 8 rules, you would have 256 rules to describe a perfect permutable 4-space quaternary ECA.

One other important thing to note about the n-space or locality of a ruleset is that the value of n, increases the number of individual computations being performed by the rules. for example, perfect permutable, 2-space, binary rules have the ruleset (00, 01, 10, 11). You may be inclined to say that there are a total of four test computations being performed by the ruleset, but this is not the case. In fact, for every element in an array ECA[n] running the perfect permutable, 2-space, binary ruleset is performing a total of ECA[n].length*2 tests. So if there are 10 elements in an array (its ECA[n].length) and the n-space is 2, you are performing a total of 20 tests. For Rule 30 which is perfect permutable, 3-space, binary, you are performing ECA[n].length*3 tests. Therefore the total number of tests is 3X the length of the array. Obviously, the runtime complexity is greater for a perfect permutable 3-space, binary ruleset than a 2-space binary ruleset. There is more computational work being done by the former ruleset because it has to perform more tests of cells in an array. If you want to be completely precise, since Rule 30 contains eight rules, each of which performs 3 tests, in the worst possible case, the algorithm for rule 30 would perform a total of (ECA[n].length*3)*8 checks. So, if an array has 10 cells, ECA[n].length = 10, and there are 3 tests per rule (checks three cells to determine the cell in the next timestep), ECA[n].length*3, and there are a total of eight rules, (ECA[n].length*3)*8, than the algorithm performs 10*3*8 tests in the worst case scenario. This is a total of 240 calculations for this particular example. To calculate the total test computations of an array of arbitrary length, we can simplify this to ECA[n].length*24. The total computations of the worst case scenario is even bigger than that. Remember that each rule also performs a set operation in the following timestep. So, the total computations performed by the Rule 30 algorithm is (ECA[n].length*24) + ECA[n].length. We added the value of the length of the array because for each element in the array, we perform one set operation in the array of the next timestep. Let's compare this to a perfect permutable 2-space binary ruleset. The permutations the ruleset tests for are (00, 01, 10, 11) so, each rule performs two test computations and one set computation. Giving a total of ((ECA[n].length*2)*4) + ECA[n].length. Assuming there are 10 elements in the ECA initial array, this gives us a total of ten elements times two tests by four rules equalling 10*2*4 or 80 total computations.

Let's also calculate the total computations of the perfect permutable 1-space binary ruleset. The equation is (ECA[n].length*2)+ECA[n].length because for an arbitrarily long array, there are two rules each performing one test and one set operation. For an array of size 10, this equals (10*2)+10 or 30 computations in a worst case scenario. That is an interesting number sequence. If we look at the total computations of Perfect Permutable n-space rulesets, at least for the first three permutables the sequence are, 30, 80, 240. What are the next numbers in the sequence? We could refine our number sequence such that each array has a length equal to the number of tests a rule must perform in n-space. What does that number sequence look like? I bet there are some interesting symmetries in that number sequence. Let's call the number sequence the Perfect Permutables Sequence. But I digress, let us return to the subject matter at hand.

ECA also have a lot in common with sorting algorithms. The difference between an ECA and a sorting algorithm (henceforth SA) is that an SA maintains the values of elements but changes those element's positions, sorting the values stored in an array. ECA do not conserve element position or element value. Thinking about this made me wonder about the permutations of possible tests, not just in n-space, but in n-position. So far we have been trying to rigorously categorize all possible ECA in terms of their rulesets. The next term I want to define is midwise. Midwise defines the position of the cell in the next timestep that is updated. Let's rigorously define n-position. In Rule 30, the n-position of R30t+1[n] is equal to the n-position of R30t[n]. This means that if we check some array element n, n-1 and n+1, in timestep t, midwise n-position means we update the cell directly below cell R30t[n] in the next timestep. Therefore, the value of R30t+1[n] is equal to the output of arbitraryRuleR(R30t[n-1], R30t[n], R30t[n+1]) at position R30t[n] in the next timestep.

R30t+1[n] = arbitraryRuleR(R30t[n-1], R30t[n], R30t[n+1])

What if instead, we changed the value of n in R30t+1[n]? We could set some other element's value, it doesn't need to be midwise! We can consider a leftwise update rule: R30t+1[n-1] = arbitraryRuleR(R30t[n-1], R30t[n], R30t[n+1]). We could consider a rightwise update rule R30t+1[n+1] = arbitraryRuleR(R30t[n-1], R30t[n], R30t[n+1]). We could consider an arbitrarily defined position to update translated by a positive or negative k: R30t+1[n+k] = arbitraryRuleR(R30t[n-1], R30t[n], R30t[n+1]). We could even set k's value to change using a for loop:

for (k = Rt.length; k > 0; k-- ){

R30t+1[k] = arbitraryRuleR(R30t[n-1], R30t[n], R30t[n+1]);

}

The for loop above would reflect each timestep over the y-axis. I'm sure this would generate an interesting ECA!

Arbitrarily defined n-position updates may be called nwise where n's value need not increment or decrement by 1. However, the for loop example above is another rule all its own. This rule is more complex than simple nwise ECA updating rules such as those of Rule 30 or any other perfect permutable, n-space, nwise ECAs. What all of this goes to show is that there is even variation in complexity of individual update rules - some update rulesets are computationally simpler than others - for instance, the comparison of perfect permutable, 2-space, midwise, binary ruleset to perfect permutable 3-space, midwise, binary ruleset. There aren't just less rules in 2-space, there are less computations (tests) that must be performed to apply a 2-space rule than a 3-space rule. The locality of the ruleset helps to determine the ruleset's runtime complexity making the rules themselves, simpler.

Look again at the ruleset for Rule 30 (above). Notice that it is the center cell in the next timestep that is being updated. This is arbitrary and one can imagine updating any cell in the next timestep as long as the 'rule' for updating is consistently applied. It wouldn't make much sense to choose a random cell to update in the next timestep. However, which one is updated can be arbitrarily defined. Midwise defines the updating of the middle cell in the next timestep At+1[n]. Leftwise - At+1[n-1], rightwise - At+1[n+1], or nwise - At+1[n+k].

A related idea to n-position is the possible cells one can test in array At[]. We can define an update rule as follows:

At+1[k] = arbitraryRuleR(At[n-1], At[n], At[n+1]);

If we look at the arbitraryRuleR(); method, we can change the arguments being passed as parameters in the method to a variety of different positions. Instead of changing the n-space, we can check (test) the n-positions of arbitrary cell positions in the array ECAt[]. For example, instead of a linear test where we test cells [n-1], [n], [n+1], we can imagine testing arbitrary positions as long as our testing system remains constant. It doesn't make sense to test random cells in an array, we should test specific cells consistently, but which cells we test can be arbitrarily defined. For example, instead of rule: At+1[k] = arbitraryRuleR(At[n-1], A30t[n], At[n+1]);

we could have: At+1[k] = arbitraryRuleR(At[n-4], At[n+6], At[n+9]);

Which cells you test is irrelevant. However, testing cells of greater distance away from n adds little, but a non-zero amount of runtime complexity since you are having to do a larger computation, which by definition, requires more computational resources (aka, larger allocation of memory).

Let's look at some results of ECA with different rulesets.

Section 2