A Simple Automaton

I created a small and silly model of computation based on a 1D cellular automaton.

June 16, 2013 - 4 minute read -
old cellular-automaton complex-systems

This is also a very very old post. It’s mostly here on this blog for personal reasons and entertainment puroses.

This is a migrated post from Wordpress so the formatting is sub optimal

A few days ago I had an idea for a simple automaton that could be used as a model of computation whose operation would be somewhat intuitive, powerful (Although not right now) and yet different from conventional models of computation to make it interesting. I am of course completely aware that this model probably is nothing more than a restatement of some other automaton. Although I would like to point out that I figured all of this out on my own though without any major interference from the real world. All of the coding has been done from scratch in Mathematica.

I will in this post give a very informal description of how the automaton works and I hope that I in a later post will be able to give you a more formal definition and a in-depth analysis of the workings of the system.

General operation

The mazer processes data in a rather simple way. The data  is stored in the ledge and is then fed down through the maze in steps(t) until it hits the ground. One can view the automaton as data "falling" through a maze.

The components

The Ledge

The so-called ledge is a rank one cyclic array of size l containing the symbols 0 or 1. The size of the ledge determines the “memory” which the machine has available.

The Ground

The ground is identical in its construction to the ledge. The ground is the final step that the machine can reach. Right now (with no jump operator) the data will definitely reach the ground eventually.

The Maze

The maze is as you might have guessed by now the actual interesting part of the system. The maze is a rank two array containing symbols from the operators alphabet. Each successive level of the maze gives a set of ordered operators which given a ledge above them determines the configuration of the ledge at the next step.

The Operators

The operators are symbols in the maze which determines the next symbol at the same position(column) as the operator. Well I can understand if you didn't really get that. Well let me put it to you like this: ThingHere we have introduced the array S which is an intermediate ledge. What we have here is that at step t the new symbol in the intermediate ledge(S) at position i  will be given by the operator located in the maze(M) at step t and position i. Said operator only takes the three symbols in L located at positions i - 1, , i + 1.

The Operator Alphabet

Given what we know above we can no start to look at the specific operators. We will use a somewhat different notation where:VariablesThis makes the description of the operators more intuitive. Below follows a list of the different operators: Untitled-1These are all the operators we will use except for  the jump operator but I will implement that later.

Example: 3-Bit Ripple-Carry Adder

Well here I will show you the code for a very simple three bit ripple-carry adder which will take two 3 bit numbers, add them and produce a 4 bit output. To do this we will connect three full-adders so obviously the first step will be to construct a simple full-adder. A full adder takes the bits A,B,C and outputs two bits S and Co where S is the sum A+B+C and Co is the carry out bit. The formula for S and Co is:

To do this we will configure the Maze as follows, With the specific positions for the input and output marked:


And then we just take three of these and connect them together using a chain of Take Left and Take Right and we get a 3-Bit adder:

Full AdderAnd isn’t that just pretty awesome! Now lets see if it works! I will just Configure the ledge to correspond to 7+5 which would in binary be 111(A)+101(B). We know that 7+5=12 so we would be expecting to see That the last four bits on the ground are 1100. So then let’s try it! Below I will show all of the steps in the operation: Adding5and7And it works! How incredibly neat!!

Whats next?

Well that’s it for this brief introduction. I will soon follow-up this post with a more detailed description on its operation and the “assembler” which I have written for the system. Later  we will also implement the special jump operator(although I might have to do a complete rewrite of the code to get that working).

And one day there will be a more popper analysis the system.

I’m fully aware that I probably explained this in the most confusing and incoherent way possible so please don’t be afraid to ask any questions or leave feedback!

Keep it Real!