*Making the simple complicated is commonplace; making the complicated simple, awesomely simple, that's creativity.* -- Charlie Mingus Cellular Automata ================= Here is a picture of the predatory snail, `Conus Textile `_: .. image:: _static/Conus_textile.JPG :target: https://en\.wikipedia\.org/wiki/Cellular_automaton#/media/File:Textile_cone\.JPG :align: center .. raw:: html
By Richard Ling - Own work; Location: Cod Hole, Great Barrier Reef, Australia, CC BY-SA 3.0, Link
The pattern on its shell is an example of a 1D cellular automata. The shell is grown by a kind of organic line of printer heads along the shell's lip. These printer heads, called pigment cells, can extrude colored calcium cement. The color choice of a pigment cell is dependent upon the color choice of it's two adjacent pigment cells. The rules governing this process are simple, yet a very complex shell color pattern emerges. A 1D cellular automata exists on a 2D grid of cells; like graphing paper, and it is governed by a simple set of rules. How you color in a square is dependent upon the coloring of the three squares above it. If we decided only to use black and white coloring, a square's color would be dependent upon eight different permutations of the three squares above it. The governing rules of a 1D cellular automata could be described by drawing out these eight pictures. But before we begin to fill in our drawings we would have to decide how to start them. Typically you color the middle square of the top line on your graphing paper black, then begin painting the squares of the second line using the rules. Of course, you don't have to do this, you can start however you like. But how you start is called the initial condition, and as you will see, the initial conditions have a huge effect on the overall emergent pattern of your drawing. In 1983 `Stephen Wolfram `_ discovered a 1D cellular automata which created patterns that look like the shell of the Conus Textile snail. He called this program, `Rule 30 `_. Let's explore how to make a Rule 30, 1D cellular automata, by looking at the instructions which govern it: *"First, look at each cell and it's right-hand neighbor. If both of these were white on the previous step, then take the new color of the cell to be whatever the previous color of its left-hand neighbor was. Otherwise, take the new color to be the opposite of that."* [#]_ Here are these instructions as a picture: .. image:: _static/rule_30_rule_in_pictures.svg :target: _static/rule_30_rule_in_pictures.pdf :align: center .. note:: If you look carefully at the picture version of the rule, you will see two rows of binary numbers, and the reason why rule 30 is called rule 30. Now let's start a drawing: we will place a black square in the middle of the first line then follow the rules to fill in the 4 lines below it. .. image:: _static/rule_30_by_hand.svg :target: _static/rule_30_by_hand.pdf :align: center If you look at the diagram and compare it to the rules described as a paragraph, then to the pictures illustrating this same rule, you will see how it works. Let's write some Python code that can build something like this. But before we start, what do we do about the edges of our graphing paper? We could just pretend they aren't there, making the automata infinite. Or, we could wrap the paper into a tube so that there is no edge. Both of these things have been done before, but I haven't seen anyone just force a color onto the edge of the graphing paper, like a wall. So, let's do that, let's build a wall. This will give us a chance to have two state machines interact in the same cellular automata. We need two different machines, a rule 30 machine and a wall machine. The wall machine should be able to be white or black. Let's design a system, then build it and run it (not necessarily in that order) and see if we can make something new. .. _cellular_automata-design: High Level Sketches ------------------- Before we start writing our code let's sketch out some pictures which will help guide our thinking. We would like to see: * :ref:`a small example of the automata running inside of walls.` * :ref:`a general idea about how to get visual feedback from our code and how that will relate to our automata.` (we will figure out the specifics later) * :ref:`some drawings of the state machines needed to make the automata.` .. _cellular_automata-a-small-example-of-the-automata-running-inside-of-walls: Automata Running Inside of Walls ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Here is a small example of the rule 30 automata running inside of walls: .. image:: _static/rule_30_basic_design_0.svg :target: _static/rule_30_basic_design_0.pdf :align: center This sketch is a mock-up of the output we would like our code to create. It also shows the rules which govern how the picture is made, some terminology and some examples about how some of the components could be build with Python. The top of the diagram describes rule 30 in pictures and the main part of the drawing shows an example of the one dimensional automata we want to build. The one dimensional automata is made up of individual cells, which will be governed by two different sets of rules. A cell can be derived from either a ``Rule30`` class which is governed by the rules described at the top of the page or a ``Wall`` class, which is given a color to start at and remains in that color forever. Once a cell is instantiated, it is started in the color we want it to appear in on our drawing. The walls of the diagram are colored orange so that we can distinguish them from the bulk of the drawing which is made up of rule 30 cells. We would like our code to be able to run for a programmable number of ``generations``. A single generation is a row of the one dimensional automata. The ``Next`` event, will be used to tell the code representing the diagram, to build its next generation. We would also like our code to be able to build any width of cells. The ``Z`` object represents the 2D binary matrix which will describe our drawing. This matrix will be used to analyze our automata as it runs. .. _cellular_automata-a-highlevel-diagram: High Level Design Diagram ^^^^^^^^^^^^^^^^^^^^^^^^^ Now that we know what kind of output we want, we need to think about how we will structure a program to give us this output. We need something that can make our one dimensional cellular automata and we need some way to look at it. Let's call the thing that we will use to visualize our automata, a canvas. Our canvas will be given an automata object which it will draw. Our automata object will have many rule 30 objects and many wall objects. Here is what we wrote above, expressed as a UML diagram: .. image:: _static/rule_30_basic_design_1.svg :target: _static/rule_30_basic_design_1.pdf :align: center The ``Canvas`` class *has a* ``OneDCellularAutomata`` class. This ``OneDCellularAutomata`` class *has many* ``Rule30`` and ``Wall`` classes. Seems simple enough. Let's build the ``Canvas`` class so that it can both draw our diagrams and make video animations. Let's make the ``OneDCellularAutomata`` responsible for creating any automata given a ``Wall`` class and a ``Rule`` class. .. _cellular_automata-state-machines-needed-to-build-automata: Statemachines Needed to Build Rule 30 in Walls ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ We have drawn the ``Rule30`` and ``Wall`` classes as abstract blocks in the previous high level diagram. But we know how they work, so let's re-draw them now in more detail: .. image:: _static/rule_30_basic_design_2.svg :target: _static/rule_30_basic_design_2.pdf :align: center The state machine under the ``Rule30`` class will provide the behaviour described by the squares at the top of the page. The state machine under the ``Wall`` class consists of two states which can only be gotten to using the ``start_at`` method, no event will cause a transition between these states. The ``Wall`` objects are intended to interface with the ``Rule30`` objects so that a ``Rule30`` cell can't tell if it is working with an actual machine or just a wall. .. _cellular_automata-design-and-code: Design and Code --------------- Now that we know what we want to build, let's make our designs more detailed and write the Python code required to make the design work. .. _cellular_automata-canvas: Canvas Class ^^^^^^^^^^^^ The ``Canvas`` class will provide visual feedback. But, how will we build a ``Canvas`` class to get the feedback needed to see what is going on with our program? If we were using Stephen Wolfram's Mathematica software, this work would be trivial. Even if we were using Matlab, it wouldn't be too hard to see these automata, but we are using Python so we will have to stitch a few things together before we can visualize our work. Let's go technology shopping. A few years ago Python `borg'd `_ Matlab, into its ``numpy``, ``scipy`` and ``matplotlib`` packages, so the Matlab type interfaces have been assimilated into the Python collective: resistance is futile. We can use the ``numpy`` and ``matplotlib`` libraries to get the Matlab features we need to build and animate our automata. The ``matplotlib`` library can animate graphs so we will use that. The graphing paper look that we want is provided by its ``matplotlib.pcolormesh`` graphing object so we will use that too. Animations are provided by the ``matplotlib.FuncAnimation`` class, which takes a reference to the figure you are drawing on, information about how many frames you want in your movie and how often you want to show them, and some callback functions that affect the data (your picture) for each frame. The callback functions will be very useful, because it means we can pull the operation of our automata away from the ``Canvas`` class and we can make the animation callback call out to a Python coroutine, so we can run our automata forever (if we wanted that). Under the hood ``matplotlib`` calls out to ``FFmpeg``, which is some open source software that makes videos. Let's install what we need and get back to our design: .. code-block:: python sudo apt-get install ffmpeg pip install numpy pip install matplotlib .. note:: I'm assuming you are working within a virtual enviroment. If you are on windows, go and get the ubuntu app, and run this code within your Windows Subsystem for Linux (WSL). If you are on a mac, you can use ``brew`` to get ffmpeg. Here is a UML drawing of the Canvas class: .. image:: _static/rule_30_canvas.svg :target: _static/rule_30_canvas.pdf :align: center The ``Canvas`` class will have a ``FuncAnimation`` object and a ``LinearSegmentedColormap`` (used for making colors), and it shows us how we want to make the object and how we want to use it with the ``run_animation`` and ``save`` methods. It also shows us that the Canvas calls will have a ``OneDCellularAutomata`` object, which will be created elsewhere, then passed to it. .. code-block:: python import pathlib import matplotlib import matplotlib.pyplot as plt import matplotlib.animation as animation class Canvas(): def __init__(self, automata, title=None): '''Animate 2D graphing paper, or static file describing a automata Given an autonoma, which has a ``_Generation`` coroutine generator, an animation can be build by calling this coroutine for as many generations are required. **Note**: This ``automata`` object needs to provide a ``_Generation`` method which returns a coroutine which can be called with ``next``. **Args**: | ``automata`` (OneDCellularAutomata): | ``title=None`` (string): An optional title **Returns**: (Canvas): this object **Example(s)**: .. code-block:: python eco1 = Canvas(autonoma) eco1.run_animation(1200, interval=10) # 10 ms eco1.save('eco1.mp4') eco2 = Canvas(automata) eco2 = save('eco2.pdf, generations=100) ''' self.fig, self.ax = plt.subplots() if title: self.ax.set_title(title) self.automata = automata self.generation = automata._Generation() self.ax.set_yticklabels([]) self.ax.set_xticklabels([]) self.ax.set_aspect(1.0) self.ax.xaxis.set_ticks_position('none') self.ax.yaxis.set_ticks_position('none') self.fig.tight_layout() # seventies orange/browns looking color map self.cmap = matplotlib.colors.LinearSegmentedColormap.from_list( 'oranges', ['#ffffff', '#ffa501', '#b27300', '#191000']) self.grid = self.ax.pcolormesh(next(self.generation), cmap=self.cmap) def init(self): '''animation initialization callback **Note**: This not needed by our animation, but it is needed by the library we are calling, so we just stub it out **Returns**: (tuple): (self.grid,) ''' return (self.grid,) def animate(self, i): '''animation callback. This method will be called for each i frame of the animation. It creates the next generation of the automata then it updates the pcolormesh using the set_array method. **Args**: | ``i`` (int): animation frame number **Returns**: (tuple): (self.grid,) ''' self.Z = next(self.generation) # set_array only accepts a 1D argument # so flatten Z before feeding it into the grid arg self.grid.set_array(self.Z.ravel()) return (self.grid,) def run_animation(self, generations, interval): '''Run an animation of the automata. **Args**: | ``generations`` (int): number of automata generations | ``interval`` (int): movie frame interval in ms **Example(s)**: .. code-block:: python eco = Canvas(automata) eco.run_animation(1200, interval=20) # 20 ms ''' self.anim = animation.FuncAnimation( self.fig, self.animate, init_func=self.init, frames=generations, interval=interval, blit=False) def save(self, filename=None, generations=0): '''save an animation or run for a given number of generations and save as a static file (pdf, svg, .. etc) **Note**: This function will save as many different static file formats as are supported by matplot lib, since it uses matplotlib. **Args**: | ``filename=None`` (string): name of the file | ``generations=0`` (int): generations to run if the files doesn't have | an 'mp4' extension and hasn't been | animated before **Example(s)**: eco1 = Canvas(autonoma) eco1.run_animation(50, 10) eco1.save('rule_30.mp4) eco1.save('rule_30.pdf) eco2 = Canvas(autonoma) eco1.save('rule_30.pdf', generations=40) ''' if pathlib.Path(filename).suffix == '.mp4': self.anim.save(filename) else: if self.automata.generation > 0: for i in range(self.automata.generations): next(self.generation) self.ax.pcolormesh(self.automata.Z, cmap=self.cmap) plt.savefig(filename) .. note:: On construction: I didn't write the ``Canvas`` class out of thin air, I created a 2 dimensional array and some functions that would randomize this array, then I fed these functions into the code that I built up using examples from the internet until I got something working. Only then did I feed it the OneDCellularAutomata class, which originally didn't use a co-routine; it was added later. .. _cellular_automata-two2Automato: The OneDCellularAutomata Class ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Let's give our basic design another look: .. image:: _static/rule_30_basic_design.svg :target: _static/rule_30_basic_design.pdf :align: center The ``OneDCellularAutomata`` object will be responsible for applying the rules to our graphing paper, and for setting it into its initial condition (the black square in the middle of the top line). To do this ``OneDCellularAutomata`` will provide a two-dimensional array, Z, containing color codes, to be used by our Canvas to draw things. It also builds a lot of ``Rule30`` and ``Wall`` state machines and links them to other machines so that they can read the ``left.color`` and ``right.color`` attributes of their adjacent cells. ``OneDCellularAutomata`` needs to set up some initial conditions; how the machines are started on the first line of our graphing paper. The ``Rule30`` state machines respond to ``Next`` events, which cause them to react and change if they need to change, so the ``OneDCellularAutomata`` will need to dispatch this event into all of the ``Rule30`` objects to make a new line as the automata propagate downward. To make the ``OneDCellularAutomata`` object generic, we will feed it its automata rule and wall rules as classes. To make the wall behaviour parameterizable, I'll add some new wall rule classes that hold the left and right colors in their class attributes: .. image:: _static/rule_30_basic_design_1.svg :target: _static/rule_30_basic_design_1.pdf :align: center Here is a UML diagram of the ``OneDCellularAutomata`` class: .. image:: _static/rule_30_twodcellularautomata.svg :target: _static/rule_30_twodcellularautomata.pdf :align: center There is a bunch of stuff in this diagram that I don't know how to draw using UML. For instance, how do I show a class that I have sent it a class, so it knows how to build something, using the class I just gave it? How do I draw something that makes a co-routine? Well, I don't know, so I will just scribble down something that isn't too confusing and explain what I meant here with a few words: The few key takeaways from the drawing are how the constructor works, we feed it in the rule and wall classes so that it can generically construct automata. We also show the function that returns the co-routine. Each time ``next`` is called it advances to the next yield statement. So, the first time the coroutine is activated, it will initialize the automata, and then every activation after that will cause it to descend one row down. Here is the code: .. code-block:: python import numpy as np from miros import Event White = 0.1 Black = 0.9 class OneDCellularAutomata(): def __init__(self, generations, cells_per_generation=None, initial_condition_index=None, machine_cls=None, wall_cls=None, ): '''Build a two dimensional cellular automata object which can be advanced with a coroutine. **Args**: | ``generations`` (int): how many generations to run (vertical cells) | ``cells_per_generation=None`` (int): how many cells across | ``initial_condition_index=None`` (int): the starting index cell (make | black) | ``machine_cls=None`` (Rule): which automata rule to follow | ``wall_cls=None`` (Wall): which wall rules to follow **Returns**: (OneDCellularAutonomata): an automata object **Example(s)**: .. code-block:: python # build an automata using rule 30 with white walls # it should be 50 cells across # and it should run for 1000 generations autonoma = OneDCellularAutomata( machine_cls=Rule30, generations=1000, wall_cls=WallLeftWhiteRightWhite, cells_per_generation=50 ) # to get the generator for this automata generation = automata.make_generation_coroutine() # to advance a generation (first one will initialize it) next(generation) # to get the color codes from it's two dimension array automata.Z # to advance a generation next(generation) ''' self.machine_cls = machine_cls self.wall_cls = wall_cls if machine_cls is None: self.machine_cls = Rule30 if wall_cls is None: self.wall_cls = WallLeftWhiteRightWhite self.generations = generations self.cells_per_generation = cells_per_generation # if they haven't specified cells_per_generation set it # so that the cells appear square on most terminals if cells_per_generation is None: # this number was discovered through trial and error # matplotlib seems to be ignoring the aspect ratio self.cells_per_generation = round(generations*17/12) self.initial_condition_index = round(self.cells_per_generation/2.0) \ if initial_condition_index is None else initial_condition_index self.generation = None self.left_wall=self.wall_cls.left_wall self.right_wall=self.wall_cls.right_wall def make_and_start_left_wall_machine(self): '''make and start the left wall based on the wall_cls''' wall = self.wall_cls() wall.start_at(self.wall_cls.left_wall) return wall def make_and_start_right_wall_machine(self): '''make and start the right wall based on the wall_cls''' wall = self.wall_cls() wall.start_at(self.wall_cls.right_wall) return wall def initial_state(self): '''initialize the 1d cellular automata''' Z = np.full([self.generations, self.cells_per_generation], Black, dtype=np.float32) # create a collections of unstarted machines self.machines = [] for i in range(self.cells_per_generation-2): self.machines.append(self.machine_cls()) left_wall = self.make_and_start_left_wall_machine() right_wall = self.make_and_start_right_wall_machine() # unstarted machines sandwiched between unstarted boundaries self.machines = [left_wall] + self.machines + [right_wall] # start the boundaries in their holding color self.machines[0].start_at(fake_white) self.machines[-1].start_at(fake_white) # start most of the machines in white except for the one at the # intial_condition_index for i in range(1, len(self.machines)-1): if i != self.initial_condition_index: self.machines[i].start_at(white) else: self.machines[i].start_at(black) # we have created a generation, so count down by one self.generation = self.generations-1 # create some initial walls in Z Z[:, 0] = self.machines[0].color_number() Z[:, Z.shape[-1]-1] = self.machines[-1].color_number() self.Z = Z def next_generation(self): '''create the next row of the 1d cellular automata''' Z = self.Z if self.generation == self.generations-1: # draw the first row for i, machine in enumerate(self.machines): Z[self.generations-1, i] = machine.color_number() else: # draw every other row Z = self.Z new_machines = [] for i in range(1, (len(self.machines)-1)): old_left_machine = self.machines[i-1] old_machine = self.machines[i] old_right_machine = self.machines[i+1] new_machine = self.machine_cls() new_machine.start_at(old_machine.state_fn) new_machine.left = old_left_machine new_machine.right = old_right_machine new_machines.append(new_machine) left_wall = self.make_and_start_left_wall_machine() right_wall = self.make_and_start_right_wall_machine() new_machines = [left_wall] + new_machines + [right_wall] for i, machine in enumerate(new_machines): machine.dispatch(Event(signal=signals.Next)) Z[self.generation, i] = machine.color_number() self.machines = new_machines[:] self.Z = Z self.generation -= 1 def make_generation_coroutine(self): '''create the automata coroutine''' self.initial_state() yield self.Z while True: self.next_generation() yield self.Z .. note:: On construction: Initially I build the ``OneDCellularAutomata`` without a coroutine. .. _cellular_automata-rule30-and-the-walls: Rule30 and the Wall Classes ^^^^^^^^^^^^^^^^^^^^^^^^^^^ ``Rule30`` is a class which describes the attributes and methods needed by our rule30 state machine. The rule30 state machine really isn't described anywhere as an individual entity, it is two callback functions that attach to a ``Rule30`` object. You can see it here: .. image:: _static/rule_30_basic_design_1.svg :target: _static/rule_30_basic_design_1.pdf :align: center To see if the rule 30 machine is designed properly, put your eyes on one of the clusters-of-four-squares at the top of the diagram. Now imagine the state machine was started in the color of the middle of the top three squares of this cluster. Send the ``Next`` event to the machine and see if you can get it to transition to the color of the bottom square of the cluster. Let's do the first one together: .. image:: _static/rule_30_does_it_work.svg :target: _static/rule_30_does_it_work.pdf :align: center If you repeat this exercise for each of the cluster-of-four-squares, and you are satisfied, then this state machine's design will give us the rule 30 behavior. The wall is an even simpler machine, it starts in one color state and remains that way forever. Here is the code for our ``Rule30`` and ``Wall`` classes: .. code-block:: python from miros import Event from miros import signals from miros import HsmWithQueues from miros import return_status class Wall(HsmWithQueues): def __init__(self, name='wall'): super().__init__(name) self.color = None def color_number(self): return Black if self.color == 'black' else White def fake_white(wall, e): status = return_status.UNHANDLED if(e.signal == signals.ENTRY_SIGNAL): wall.color = 'white' status = return_status.HANDLED elif(e.signal == signals.Next): status = return_status.HANDLED else: wall.temp.fun = wall.top status = return_status.SUPER return status def fake_black(wall, e): status = return_status.UNHANDLED if(e.signal == signals.ENTRY_SIGNAL): wall.color = 'black' status = return_status.HANDLED elif(e.signal == signals.Next): status = return_status.HANDLED else: wall.temp.fun = wall.top status = return_status.SUPER return status class WallLeftWhiteRightWhite(Wall): left_wall = fake_white right_wall = fake_white class WallLeftWhiteRightBlack(Wall): left_wall = fake_white right_wall = fake_black class WallLeftBlackRightWhite(Wall): left_wall = fake_black right_wall = fake_white class WallLeftBlackRightBlack(Wall): left_wall = fake_black right_wall = fake_black class Rule30(Wall): def __init__(self, name='cell'): super().__init__(name) self.left = None self.right = None self.color = None def white(cell, e): status = return_status.UNHANDLED if(e.signal == signals.ENTRY_SIGNAL): cell.color = 'white' status = return_status.HANDLED elif(e.signal == signals.Next): if((cell.right.color == 'black' and cell.left.color == 'white') or (cell.right.color == 'white' and cell.left.color == 'black')): status = cell.trans(black) else: status = return_status.HANDLED else: cell.temp.fun = cell.top status = return_status.SUPER return status .. _cellular_automata-running-and-visualizing-the-automata: Running and Visualizing the Cellular Automata --------------------------------------------- Now that we have all the parts we need let's stitch them together and see what happens. We will build an automata using rule 30 with some white walls. Then we will feed the automata into a canvas, and use the canvas to print a `png` file, a `pdf` file and an `mp4` movie: .. code-block:: python generations = 200 automata = OneDCellularAutomata( generations=generations, machine_cls=Rule30, wall_cls=WallLeftWhiteRightWhite) ecosystem = Canvas(automata) ecosystem.run_animation(generations, interval=100) # 100 ms eco.save('rule_30_white_walls_200_generations.mp4') eco.save('rule_30_white_walls_200_generations.pdf') eco.save('rule_30_white_walls_200_generations.png') Here is the movie: .. raw:: html
Here is the `pgn` diagram, click on it to see the `pdf` version of the same picture: .. image:: _static/rule_30_white_walls_200_generations.png :target: _static/rule_30_white_walls_200_generations.pdf :align: center Let's try it with black walls .. code-block:: python generations = 200 automata = OneDCellularAutomata( generations=generations, machine_cls=Rule30, wall_cls=WallLeftBlackRightBlack) ecosystem = Canvas(automata) ecosystem.run_animation(generations, interval=50) # 50 ms eco.save('rule_30_black_walls_200_generations.mp4') eco.save('rule_30_black_walls_200_generations.pdf') eco.save('rule_30_black_walls_200_generations.png') Here is a `link `_ to the resulting video, and below you can see what happens when we run 200 generations of rule 30 with black walls. .. image:: _static/rule_30_black_walls_200_generations.png :target: _static/rule_30_black_walls_200_generations.pdf :align: center `Running it again for 500 generations `_ and with white walls results in this: .. image:: _static/rule_30_white_walls_500_generations.png :target: _static/rule_30_white_walls_500_generations.pdf :align: center On this diagram we can see order imposing itself from the left white wall, and a `kind of repeating pattern on the left side of the triangle `_ which emerges from our initial conditions. The center and right part of the results seem to be full of disorder. .. note:: On limitations: The pdf resulting from the 500 generation run of our automata is over 5 MB; this is a lot of data to add to your computer if you want to clone the miros library, so I will refrain from going bigger. It took a long time to render the 500 generation automata. I don't know where the computational bottle-neck is coming from; if it were important to me I could profile the different parts of the code until I found my issue, but the issue could be Python itself. Mathematica has no such obvious limitation. If you want to do a deep dive into this subject and don't have the resources to buy a Mathematica licence, you can buy a Raspberry Pi with the NOOBs OS, then VNC onto the device from your desktop. Wolfram Alpha is being given away on this platform. .. _cellular_automata-the-nothing: The Nothing (n-phenomenon) -------------------------- The white and black walls force order into the automata; causing a kind of pattern crystallization to propagate across our results. We lose the incredible complexity of rule 30, to this ordering pattern, which I think of as the `nothing `_. Order imposes itself like a prion does in the brain of someone with Alzheimer's. We have seen that this effect takes place with both white and black walls, the key is that there is an inflexible minority on the walls, imposing itself on a flexible majority. (Nassim Nicholas Taleb calls this kind of thing `a normalization `_.) I will call this destructive ordering, the n-phenomenon. .. note:: Our universe seems to have set rules (the laws of physics) but it will not run into this n-phenomenon, repetition issue; because it doesn't seem to be confined within walls or have limited memory: the universe is expanding at an accelerating rate. Maybe it would have been wiped out by an n-phenomenon if it weren't expanding. Let's study it in a bit more detail. I will shrink the width of our graphing paper to 30 cells and watch the n-phenomenon completely destroy rule 30's beautiful complexity over 100 generations. .. code-block:: python :emphasize-lines: 7 generations = 100 automata = OneDCellularAutomata( generations=generations, machine_cls=Rule30, wall_cls=WallLeftWhiteRightWhite, cells_per_generation=30) ecosystem = Canvas(automata) ecosystem.run_animation(generations, interval=500) # 500 ms eco.save('rule_30_white_walls_100_generations_width_30.mp4') .. raw:: html
It seems that the n-phenomenon has a pattern velocity; resulting in an angle. My protractor tells me that the ordered crystallization, caused by the white minority at the wall, spreads downward at an angle of about 20 degrees. If we reduce the width of the graphing paper, this pattern seems to advance quicker into the chaos: .. code-block:: python :emphasize-lines: 7 generations = 100 automata = OneDCellularAutomata( generations=generations, machine_cls=Rule30, wall_cls=WallLeftWhiteRightWhite, cells_per_generation=15) ecosystem = Canvas(automata) ecosystem.run_animation(generations, interval=500) # 500 ms eco.save('rule_30_white_walls_100_generations_width_30.mp4') Compare the 30 cell width result to the 15 cell width result: .. raw:: html
Let's try going thinner, here is a 15 cell width result beside a 10 cell width result: .. raw:: html
So the angle of the n-phenomenon does not necessarily shrink with a reduction in the graphing paper's width. Let's write some code that can calculate the angle of the n-phenomenon. We will set the walls to be white and the initial condition is a single black rule 30 machine, sandwiched between other rule 30 machines started in the white state: .. image:: _static/rule_30_twodcellularautomata_with_angle.svg :target: _static/rule_30_twodcellularautomata_with_angle.pdf :align: center The blue object in the diagram represents the disordered part of a rule 30 simulation contained by white walls. The cyan circle is the angle, in degrees, we are searching for. .. code-block:: python class OneDCellularAutomataWithAngleDiscovery(OneDCellularAutomata): def __init__(self, generations, cells_per_generation=None, initial_condition_index=None, machine_cls=None, wall_cls=None): super().__init__( generations, cells_per_generation, initial_condition_index, machine_cls, wall_cls) self.black_mask = np.array([Black], dtype=np.float32) self.white_mask = np.array([White], dtype=np.float32) self.n_mask = np.concatenate( (self.white_mask, self.black_mask), axis=0) self.n_angle = 90 def build_next_mask(self): if abs(self.n_mask[-1] - White) < 0.001: self.n_mask = np.concatenate( (self.n_mask, self.black_mask), axis=0) else: self.n_mask = np.concatenate( (self.n_mask, self.white_mask), axis=0) def update_angle(self): previous_generation = self.generation+1 row_to_check = self.Z[previous_generation] sub_row_to_check = row_to_check[0:len(self.n_mask)] if np.array_equal(self.n_mask, sub_row_to_check): self.nothing_at_row = self.generations-previous_generation + 1 adjacent = self.nothing_at_row - self.cells_per_generation / 2.0 opposite = self.cells_per_generation self.n_angle = math.degrees(math.atan(opposite/adjacent)) self.build_next_mask() def next_generation(self): super().next_generation() self.update_angle() With this code we can plot how the angle of the n-phenomenon changes as a function of the graphing paper width: .. image:: _static/cells_per_generation_vrs_angle_of_n_phenomenon.svg :target: _static/cells_per_generation_vrs_angle_of_n_phenomenon.pdf :align: center .. note:: The angle is still an approximation, since as you will see shortly, the n-phenomenon is not a straight line. Here is a video of 196 different renderings of rule thirty within white walls. The video starts with 2 rule 30 machines squished between two white walls. For each frame advance of the video, a cell is added to the width of the graphing paper and the automata is restarted an run with a black machine at the top and middle of the simulation. .. raw:: html
The top part of the video remains constant as the width of the graphing paper expands, which makes sense, since that part of the diagram experiences the same set of initial conditions. What is surprising is how avalanches perpetuate through the diagram as the width of the graphing paper increases. The left side will cause an avalanche for two frames, then the right side will cause an avalanche for two frames, then the left side again and so on and so forth. You can see when the patterns are going to shift by watching for the "left white _|" and the "black right L". If either of these mini-patterns appear, it will tell you that the avalanche on their side of the diagram is over, and to move your eyes to the other side of the page for the next frame. As tempting as it is to think that this 2 beat oscillation is a feature of the automata, it probably isn't. The 2 beat oscillation is the result of the divide-by-2-and-round-the-result mixed with the expansion-of-the-size-of-the-page. Essentially we are changing the initial conditions on one side of the page for 2 beats, then the other side for two beats. Because rule 30 creates a chaotic system that is highly sensitive to its initial conditions we have avalanches of change in response to a new partial-starting-state. The initial conditions remain the same for the top part of the diagram, but are expressed when the rule 30 body hits the new wall condition. The video makes me think about time traveling stories. If we imagine the new starting condition as the location of a time traveler arriving in the past from the future (to change one thing and then leave), we can see how he effects history as the change-avalanche on his side of the video frame. The entire past isn't changed, just the side that was within the causal cone of his avalanche. The rule 30 states only one square can be effected each generation; so the maximum theoretical propagation of a historical distortion is 45 degrees. In our reality we also have such a causal limitation, it is the speed of light, c. Here is another video of 196 different renderings with a white left wall and black right wall: .. raw:: html
Black left, white right wall: .. raw:: html
Left and right walls set to black: .. raw:: html
Random Number Generation ========================== Let's try and build a random number generator using a simple Python program. First we should discuss our constraints. Rule 30 provides an interesting chaotic phenomenon, we would like to use this rule versus another rule, or we may accidentally lose our ability to generate chaos. If we make our graphing paper very wide, then we need more computer memory and more computing resources to construct the next generation of automata. If we use walls, then we have order imposing itself back into the body of the chaos, as the n-phenomenon, over only a few generations. Even if we can perfectly manage this n-phenomenon, there are only so many permutations that can be held within the bounds of our rectangle, and if we repeat a pattern we are not generating a random number, but rather a long periodic number; a pseudo-random number. So there seems to be a theoretical upper bound to what we can generate using limited memory given that the rule doesn't change and the state of the program is held within a bounded rectangle. My first guess at what our upper bound is: ``2**n`` where ``n`` is the number of states within the rectangle, and the ``2`` is selected because we are only tracking two colors, black and white. First things first, let's deal with the n-phenomenon coming from the walls. We have control of the walls, and we have a chaos generator, so let's mine the chaos and feed it back into the walls. .. image:: _static/rule_30_chaos_to_walls_1.svg :target: _static/rule_30_chaos_to_walls_1.pdf :align: center We can write the colors of our center column into a deque, and use the top two colors of this deque to set the color of the walls. Let's call this deque the ``core_colors``. To begin with we set all of the ``core_colors`` to white, so that the walls will remain white for at least the first ``len(core_colors) - 2`` generations. For every ``Next`` event, the ``core_colors`` deque is pushed one spot downward into the center of our automata, where it is painted with the color of the core at that spot. We will use the last two elements of our ``core_colors`` to determine the color of our walls. These last two spots will act as a 2 digit binary number, holding the values of ``WallLeftWhiteRightWhite``, ``WallLeftWhiteRightBlack``, ``WallLeftBlackRightWhite`` and ``WallLeftBlackRightBlack``. How this rule is applied isn't that important, it just has to consistently map the center's chaos onto the walls. So, how long do we make this ``core_colors`` deque? My intuition is to feed it as much chaos as rule 30 can generate, then feed this back into the automata before the n-phenomenon destroys the disorder. I predict that we will have a very long unique pattern when the length of the center column's deque depth is equal to the number of cells from the top to where the n-phenomenon eats away the chaos. I will mark this queue depth estimate with a ``*`` in my data. .. note:: You might be asking yourself, "Why don't we pull the chaos from its deepest well: the far right side of the bulk of the rule 30 cells in the body of our automata." I was originally going to do this, until I saw the effect of the time traveler videos in the previous section. The cone of causality propagates from the walls. If we mine the chaos from the right side, there won't be a chance for the rule30 interactions on the right side to feel the effect of the bulk and as a result we will end up with a very narrow feedback loop despite having a deeper deque. This theory could be tested and disproved, but my program is inefficient and my computer is very slow, so I took the center path. The length of the unique pattern duration will be too much to measure manually, so I will adjust the code to report the unique pattern duration for a specific combination of cell width and queue depth. I'll explain how I did this after I present my data and results. Let's start with the discovered data: +----------------------+------------+--------------------------+----------+ | Cell Width and angle | Queue Depth| Unique Pattern Duration | Repeats? | +======================+============+==========================+==========+ | 10 (35.7 degrees) | 2 | 37 | True | + + + + + | | 3 | 51 | | + + + + + | | 4 | 14 | | + + + + + | | 5 | 16 | | + + + + + | | 6 | 35 | | + + + + + | | 7 | 30 | | + + + + + | | 8 | 65 | | + + + + + | | 9 | 24 | | + + + + + | | 10* | 52 | | + + + + + | | 11 | 110 | | + + + + + | | 12 | 30 | | + + + + + | | 13 | 32 | | +----------------------+------------+--------------------------+----------+ | 11 (44.4 degrees) | 2 | 53 | True | + + + + + | | 3 | 5 | | + + + + + | | 4 | 24 | | + + + + + | | 5 | 57 | | + + + + + | | 6 | 28 | | + + + + + | | 7 | 30 | | + + + + + | | 8 | 32 | | + + + + + | | 9 | 27 | | + + + + + | | 10 | 36 | | + + + + + | | 11 | 42 | | + + + + + | | 12 | 80 | | + + + + + | | 13* | 42 | | + + + + + | | 14 | 84 | | + + + + + | | 15 | 46 | | + + + + + | | 16 | 48 | | + + + + + | | 17 | 50 | | + + + + + | | 18 | 52 | | +----------------------+------------+--------------------------+----------+ | 12 (36.0 degrees) | 2 | 16 | True | + + + + + | | 3 | 35 | | + + + + + | | 4 | 24 | | + + + + + | | 5 | 26 | | + + + + + | | 6 | 39 | | + + + + + | | 7 | 58 | | + + + + + | | 8 | 19 | | + + + + + | | 9 | 14 | | + + + + + | | 10 | 46 | | + + + + + | | 11 | 36 | | + + + + + | | 12* | 53 | | + + + + + | | 13 | 32 | | + + + + + | | 14 | 42 | | + + + + + | | 15 | 276 | | + + + + + | | 16 | 46 | | + + + + + | | 17 | 13 | | + + + + + | | 18 | 25 | | +----------------------+------------+--------------------------+----------+ | 13 (36.0 degrees) | 2 | 16 | True | + + + + + | | 3 | 5 | | + + + + + | | 4 | 9 | | + + + + + | | 5 | 12 | | + + + + + | | 6 | 46 | | + + + + + | | 7 | 34 | | + + + + + | | 8 | 15 | | + + + + + | | 9 | 65 | | + + + + + | | 10 | 139 | | + + + + + | | 11 | 24 | | + + + + + | | 12* | 44 | | + + + + + | | 13 | 121 | | + + + + + | | 14 | 35 | | + + + + + | | 15 | 157 | | + + + + + | | 16 | 318 | | + + + + + | | 17 | 465 | | + + + + + | | 18 | 278 | | + + + + + | | 19 | 76 | | + + + + + | | 20 | 225 | | + + + + + | | 21 | 197 | | + + + + + | | 22 | 384 | | + + + + + | | 23 | 30 | | + + + + + | | 24 | 162 | | +----------------------+------------+--------------------------+----------+ | 14 (30.2 degrees) | 2 | 42 | True | + + + + + | | 3 | 43 | | + + + + + | | 4 | 13 | | + + + + + | | 5 | 20 | | + + + + + | | 6 | 26 | | + + + + + | | 7 | 9 | | + + + + + | | 8 | 32 | | + + + + + | | 9 | 176 | | + + + + + | | 10 | 271 | | + + + + + | | 11 | 279 | | + + + + + | | 12 | 20 | | + + + + + | | 13* | 236 | | + + + + + | | 14 | 395 | | + + + + + | | 15 | 66 | | + + + + + | | 16 | 208 | | + + + + + | | 17 | 13 | | + + + + + | | 18 | 338 | | + + + + + | | 19 | 195 | | + + + + + | | 20 | 228 | | + + + + + | | 21 | 98 | | + + + + + | | 22 | 210 | | + + + + + | | 23 | 255 | | + + + + + | | 24 | 1450 | | + + + + + | | 25 | 32 | | + + + + + | | 26 | 1223 | | + + + + + | | 27 | 287 | | + + + + + | | 28 | 1012 | | + + + + + | | 29 | 610 | | +----------------------+------------+--------------------------+----------+ | 15 (39.2 degrees) | 4 | 44 | True | + + + + + | | 5 | 160 | | + + + + + | | 6 | 134 | | + + + + + | | 7 | 60 | | + + + + + | | 8 | 58 | | + + + + + | | 9 | 48 | | + + + + + | | 10 | 52 | | + + + + + | | 11 | 200 | | + + + + + | | 12 | 160 | | + + + + + | | 13 | 74 | | + + + + + | | 14 | 429 | | + + + + + | | 15 | 541 | | + + + + + | | 16* | 1022 | | + + + + + | | 17 | 73 | | + + + + + | | 18 | 17 | | + + + + + | | 19 | 271 | | + + + + + | | 20 | 232 | | + + + + + | | 21 | 534 | | + + + + + | | 22 | 564 | | + + + + + | | 23 | 1210 | | + + + + + | | 24 | 258 | | + + + + + | | 25 | 630 | | +----------------------+------------+--------------------------+----------+ | 16 (34.0 degrees) | 2 | 111 | True | + + + + + | | 3 | 18 | | + + + + + | | 4 | 42 | | + + + + + | | 5 | 123 | | + + + + + | | 6 | 74 | | + + + + + | | 7 | 35 | | + + + + + | | 8 | 288 | | + + + + + | | 9 | 310 | | + + + + + | | 10 | 42 | | + + + + + | | 11 | 582 | | + + + + + | | 12 | 46 | | + + + + + | | 13 | 40 | | + + + + + | | 14 | 86 | | + + + + + | | 15 | 252 | | + + + + + | | 16* | 378 | | + + + + + | | 17 | 180 | | + + + + + | | 18 | 900 | | + + + + + | | 19 | 288 | | + + + + + | | 20 | 541 | | + + + + + | | 21 | 1746 | | + + + + + | | 22 | 1017 | | + + + + + | | 23 | 117 | | + + + + + | | 24 | 1162 | | + + + + + | | 25 | 551 | | + + + + + | | 26 | 1182 | | +----------------------+------------+--------------------------+----------+ | 17 (35.3 degrees) | 5 | 36 | True | + + + + + | | 6 | 47 | | + + + + + | | 7 | 270 | | + + + + + | | 8 | 164 | | + + + + + | | 9 | 92 | | + + + + + | | 10 | 42 | | + + + + + | | 11 | 179 | | + + + + + | | 12 | 433 | | + + + + + | | 13 | 448 | | + + + + + | | 14 | 238 | | + + + + + | | 15 | 120 | | + + + + + | | 16 | 60 | | + + + + + | | 17 | 1054 | | + + + + + | | 18* | 441 | | + + + + + | | 19 | 1149 | | + + + + + | | 20 | 390 | | + + + + + | | 21 | 1582 | | + + + + + | | 22 | 600 | | + + + + + | | 23 | 3305 | | + + + + + | | 24 | 214 | | + + + + + | | 25 | 2810 | | +----------------------+------------+--------------------------+----------+ | 18 (27.7 degrees) | 4 | 97 | True | + + + + + | | 5 | 90 | | + + + + + | | 6 | 158 | | + + + + + | | 7 | 82 | | + + + + + | | 8 | 192 | | + + + + + | | 9 | 319 | False | + + + + + | | 10 | 70 | True | + + + + + | | 11 | 101 | True | + + + + + | | 12 | 200 | True | + + + + + | | 13 | 586 | True | + + + + + | | 14 | 597 | True | + + + + + | | 15 | 24 | True | + + + + + | | 16 | 430 | True | + + + + + | | 17* | 860 | True | + + + + + | | 18 | 459 | True | + + + + + | | 19 | 605 | True | + + + + + | | 20 | 532 | True | + + + + + | | 21 | 609 | True | + + + + + | | 22 | 2356 | True | + + + + + | | 23 | 1730 | True | + + + + + | | 24 | 908 | True | + + + + + | | 25 | 734 | True | + + + + + | | 26 | 1513 | True | + + + + + | | 27 | 1653 | True | + + + + + | | 28 | 165 | True | + + + + + | | 29 | 954 | True | + + + + + | | 30 | 682 | True | +----------------------+------------+--------------------------+----------+ | 19 (27.5 degrees) | 4 | 11 | True | + + + + + | | 5 | 75 | | + + + + + | | 6 | 91 | | + + + + + | | 7 | 99 | | + + + + + | | 8 | 43 | | + + + + + | | 9 | 33 | | + + + + + | | 10** | 33 | | + + + + + | | 11 | 144 | | + + + + + | | 12 | 134 | | + + + + + | | 13 | 70 | | + + + + + | | 14 | 252 | | + + + + + | | 15 | 250 | | + + + + + | | 16 | 155 | | + + + + + | | 17 | 677 | | + + + + + | | 18* | 1943 | | + + + + + | | 19 | 1299 | | + + + + + | | 20 | 130 | | + + + + + | | 21 | 2689 | | + + + + + | | 22 | 5168 | | + + + + + | | 23 | 1602 | | + + + + + | | 24 | 922 | | + + + + + | | 25 | 2080 | | + + + + + | | 26 | 2895 | | + + + + + | | 27 | 5341 | | + + + + + | | 28 | 3520 | | +----------------------+------------+--------------------------+----------+ | 20 (27.5 degrees) | 4 | 11 | True | + + + + + | | 5 | 75 | | + + + + + | | 6 | 91 | | + + + + + | | 7 | 99 | | + + + + + | | 8 | 43 | | + + + + + | | 9 | 279 | | + + + + + | | 10 | 213 | | + + + + + | | 11 | 202 | | + + + + + | | 12 | 327 | | + + + + + | | 13 | 792 | | + + + + + | | 14 | 490 | | + + + + + | | 15 | 1436 | | + + + + + | | 16 | 1349 | | + + + + + | | 17 | 556 | | + + + + + | | 18* | 1171 | | + + + + + | | 19 | 172 | | + + + + + | | 20 | 333 | | + + + + + | | 21 | 2912 | | + + + + + | | 22 | 2054 | | + + + + + | | 23 | 5769 | | + + + + + | | 24 | 1546 | | + + + + + | | 25 | 579 | | + + + + + | | 26 | 400 | | + + + + + | | 27 | 4535 | | + + + + + | | 28 | 9075 | | + + + + + | | 29 | 9709 | | + + + + + | | 30 | 1697 | | +----------------------+------------+--------------------------+----------+ | 21 (27.5 degrees) | 2 | 615 | True | + + + + + | | 3 | 333 | | + + + + + | | 4 | 2912 | | + + + + + | | 5 | 422 | | + + + + + | | 6 | 534 | | + + + + + | | 7 | 113 | | + + + + + | | 8 | 429 | | + + + + + | | 9 | 82 | | + + + + + | | 10 | 79 | | + + + + + | | 11 | 551 | | + + + + + | | 12 | 862 | | + + + + + | | 13 | 2159 | | + + + + + | | 14 | 91 | | + + + + + | | 15 | 526 | | + + + + + | | 16 | 1327 | | + + + + + | | 17 | 837 | | + + + + + | | 18 | 1429 | | + + + + + | | 19* | 1173 | | + + + + + | | 20 | 220 | | + + + + + | | 21 | 3706 | | + + + + + | | 22 | 300 | | + + + + + | | 23 | 27 | | + + + + + | | 24 | 3090 | | + + + + + | | 25 | 6036 | | + + + + + | | 26 | 44 | | + + + + + | | 27 | 3416 | | + + + + + | | 28 | 9032 | | + + + + + | | 29 | 2067 | | + + + + + | | 30 | 9151 | | +----------------------+------------+--------------------------+----------+ | 22 (24.0 degrees) | 2 | 113 | True | + + + + + | | 3 | 58 | True | + + + + + | | 4 | 350 | True | + + + + + | | 5 | 120 | True | + + + + + | | 6 | 197 | False | + + + + + | | 7 | 135 | False | + + + + + | | 8 | 169 | False | + + + + + | | 9 | 47 | True | + + + + + | | 10 | 123 | False | + + + + + | | 11 | 330 | False | + + + + + | | 12 | 219 | True | + + + + + | | 13 | 981 | False | + + + + + | | 14 | 569 | False | + + + + + | | 15 | 763 | False | + + + + + | | 16 | 398 | False | + + + + + | | 17 | 694 | True | + + + + + | | 18 | 584 | True | + + + + + | | 19 | 373 | True | + + + + + | | 20 | 357 | False | + + + + + | | 21 | 759 | False | + + + + + | | 22 | 433 | False | + + + + + | | 23 | 266 | False | + + + + + | | 24 | 204 | True | + + + + + | | 25 | 4395 | False | + + + + + | | 26 | 527 | True | + + + + + | | 27 | 1138 | True | + + + + + | | 28 | 3383 | False | + + + + + | | 29 | 3562 | False | + + + + + | | 30 | 148 | False | + + + + + | | 31 | 4611 | False | +----------------------+------------+--------------------------+----------+ .. note:: ``**`` means, that there is a kind of n-phenomenon pattern that emerges after some time, but before this occurs there is a a nice, richly chaotic pattern. So, my prediction wasn't terrible. It turns out that as far as guesses go, if we set the ``core_color`` deque length to the number of cells from the top of the automata to where the n-phenomenon would overtake the chaos (leaving the walls white), then you get some decent periodicity. However, we consistently observed that just above my predicted optimal number, there is a very large swell in the length of unique pattern duration. Another strange thing was observed: the length of a unique pattern duration increases as we increase the ``core_color`` deque length. In some cases we seem to be getting massive gains with tiny marginal increases in the ``core_color`` deque length. Are we getting something from nothing? No, it turns out you get massive increases in the unique pattern duration but you don't have consistent chaos in the pattern: the chaos is marbled with the n-phenomenon. You can see this effect in this video of rule 30 within recursive walls, 12 cells wide, with a ``core_color`` deque length of 40, run for 400 generations (settles into a loop of 47 cells): .. raw:: html
There are other incidence were a different repeating pattern emerges after a long burst of rich chaos. The repeating pattern is much more complex than the n-phenomenon, but much less complex than its preceding chaos. For width 22 we see something really cool. The chaos just stops, there is no repetition of a complex pattern, we get to see it once, then never again. This has a nice effect of hiding the pattern's duration from my autocorrelation routine. To measure the duration of the chaos burst I had to manually read it from the picture, this was very time consuming. For width 22, the ``core_color`` deque is often infected with the n-phenomenon despite our best efforts to feed it's chaos into the walls. Given that this phenomenon was discovered within the first 12 tested rectangle widths, it is not unreasonable to assume that is a common occurrence; there will probably be a lot of widths and queue depth combinations that result in the ultimate destruction of the chaos generator. You can see this effect in this video of rule 30 within recursive walls, 22 cells wide, with a ``core_color`` deque length of 20, run for 400 generations (one unique pattern for 357 cells): .. raw:: html
.. [#] Stephen Wolfram (2002). `A New Kind of Science. `_ (p27)