Cellular Automata

Cellular automata (CA) are structures that change based on very simple rules. In this blog post, I've implemented a demo that sets the background to a one-dimensional CA.

One-dimensional CA were first popularized by Stephen Wolfram, who wrote a book about them called A New Kind of Science. It's quite lengthy, but there are tons of cool pictures and lots of new ideas (I had never even heard of 1D CA before reading it). For example, the 1D CA with neighbor distance $1$ and rule $01101110_2=110_{10}$ (if you don't know what these terms mean just hang tight) is capable of simulating all computable functions, meaning given enough resources, it's basically a computer. I've yet to use rule $110_{10}$ for computation, but it certainly looks very cool (see for yourself below).

Demo

I recommend leaving all the boxes blank for your first run. Defaults will be inserted in blank boxes. Then you can play around with the values to see what each option does. Note: colors must be input in the following format, "#FE624A". If you're on a mobile device, I recommend clicking the image link for optimal viewing.





Image link: none

To save the background image, click on the link and type ctrl+s. If you want to generate another random rule, make sure to delete the current one.

How do One-dimensional Cellular Automata Work?

Start out with a row of zeroes and ones.
\(\require{color}\) $$1010101110$$ Add a row of blank spots beneath it to denote the next generation. We can make two-dimensional images by stacking subsequent generations on top of each other.
$$1010101110$$ $$0000000000$$ For each $0$ in our new row, we're going to look at the previous row to decide whether or not it stays a $0$ or becomes a $1$. Here's where the "Neighbor distance" part comes in: we're only going to look at bits in the vicinity of the bit directly above the current $0$.
$$101\color{red}010\color{black}1110$$ $$0000\color{red}0\color{black}00000$$ We look at the bit directly above no matter what. But see how our view extends one to the left and one to the right? That's the neighbor distance. So now we need to decide whether or not the current $0$ should be a $1$ based on the pattern $010$. How do we do that? It's super easy. Cellular automata are defined by their rules, and their rules tell us exactly which patterns get turned into $1$s. I won't describe this in too much detail, but imagine listing out every possible pattern for a given neighbor distance:
$$000,001,010,011,100,101,110,111$$ And highlighting the patterns that you want to result in $1$s.
$$000,001,\color{red}010\color{black},011,100,101,\color{red}110\color{black},111$$ Now, write $0$s for all the unhighlighted patterns and $1$s for those that are.
$$\text{Rule: }00100010$$ All we have to do is apply this rule a million times and we'll have a nice new background image to show off. Aren't you glad you're not a computer?

Fork me on GitHub


comments powered by Disqus