\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{anyfontsize}
\usepackage[super]{nth}
\usepackage{ulem}
\usepackage{multicol}
\usepackage{phaistos}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage[all,arc]{xy}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\usepackage[font={small,it}]{caption}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\begin{document}
\title{Cellular Automata}
\author{Nicholas Geis}
\date{\today}
\maketitle
In Stephen Wolfram's book, \textit{A New Kind of Science}, he postulates that the world as we know it and all its complexities is just a simple Sequential Dynamical System that is governed by a very simple set of rules. All of Physics, all of Biology, all of Mathematics are interlinked through those simple rules. Now, that seems just absolutely absurd and downright crazy. How can such a simple set of rules form the complex theories of Mathematics and Physics and the seemingly random processes of Biology? This week, we will examine the field that Wolfram himself forged and look at how simple rules can lead to very complicated structures. This field is called Cellular Automata.\\
\\
Now, what exactly is Cellular Automata? Cellular Automata, or CA\footnote{This abbreviation is the accepted shorten for Cellular Automata}, has several features that are similar to the features of an SDS. These are traits that they share:
\begin{enumerate}
\item There is a collection of vertices that are from the set $V$.
\item There is a set, $S$, that characterizes the states of said vertices. For most CA, that set is $S=\{0,1\}$. Those are the simplest of states and the ones that we will be working with the most in this class.
\item There is a defined function $f_v$ that interacts with the vertices to output a new vertex or update an older one.
\end{enumerate}
From there, differences start to arise between the two. Those differences include
\begin{enumerate}
\item Unlike SDS, CA always updates simultaneously. As in, each vertex updates at the same time. Each update is usually seen as one time step forward and thus the system evolves in discrete time steps.
\item CA usually consists of uniform structure\footnote{This is intended because it includes translation invariance. Which implies that, at least in one direction, the object is infinite. As in, for any point \textbf{p}, the set of points with the same properties due to translational symmetry form the infinite discrete set $\{\textbf{p} +\textit{n} \textbf{a} | \textit{n} \in \mathbb{Z}\} = \textbf{p} + \mathbb{Z} \textbf{a}$ (Wikipedia [4]).}, and as a result, all graphs that define a CA are always regular graphs. For example, $\mathbb{Z}^k$ where $k>1$. This produces the simple geometric grid that everyone knows and loves when $k=2$.
\item The edges of the graph form neighborhoods with all adjacent vertices. In general, we define a neighborhood, $n[v]$, as follows:\\
We take a sequence $N$ and define it as $N=( d_1, ..., d_m)$, where $d_i \in Y$ and $Y$ is our strongly regular graph. Then define $n[v]$ to be 
$$n[v]=v+N=(v+d_1, ... , v+d_m).$$
In short, take whatever grid structure your Graph, $Y$, and let the neighbors of $v$ be what you think they are. Just the points on the grid surrounding vertex $v$. That's your neighborhood in $\mathbb{Z}^2$. However, changes can be brought to this definition that allow for a different idea of neighborhoods. The two most commonly used definitions are the von Neumann neighborhood and the Moore neighborhood. To put them simply, the von Neumann neighborhood for a basic grid structure in $\mathbb{Z}^2$ is the center box and then the boxes that border its sides. Only those 5 boxes constitute the neighborhood. And the Moore neighborhood is the von Neumann neighborhood with the addition of the corner boxes. So it forms a 3X3 grid of boxes that is made up of 9 squares.
\begin{figure}[h]
\includegraphics[width=0.8\textwidth]{neighborhoods.png}
\caption{(a) is the von Neumann neighborhood and (b) is the Moore neighborhood.}
\end{figure}
\end{enumerate}
Those are the main similarities and differences between CA and SDS (Wolfram [2]). From here, we will continue to work with CA but only in the simplest cases (most likely for the rest of the quarter). The simplest of CA actually have a formal name. They are called the Elementary CA.\\
\\
These are the following rules to Elementary CA:
\begin{enumerate}
\item Our graph will be $\mathbb{Z}^2$. In this graph, each box will belong to our set of vertices $V$. And the states of each vertex is in $S$ and $S=\{0,1\}$.
\item Our function $f$ will map the following
$$f \ : \ \mathbb{F}_2^3 \ \rightarrow \ \mathbb{F}_2$$
where $\mathbb{F}_2=\{0,1\}$. In layman's terms, we are taking a string of length 3 that has a combination of 1's and 0's in it and mapping it to either a 1 or a 0.
\item Our neighborhoods will consist of a vertex, $v$, and the vertices to the right and to the left. Only 3 blocks will belong to each neighborhood.
\end{enumerate}
Those are the rules to Elementary CA (Mortveit [1]). Now, some may ask how many different configurations are there for Elementary CA and how can we possible name each one in an organized manner? Well I will show you.\\
\\
\textit{Claim}: There are 256 possible CA configurations that follow the Elementary rules.\\
\\
\textit{Proof}: This is actually quite trivial. We know that we get to choose if there is a 1 or a 0 for the mapping so we have 2 choices but how many things are we mapping. In short, we are doing the following
$$\# \ of \ configurations \ = \ |\mathbb{F}_2|^{|\mathbb{F}_2^3|}=2^8=256.$$
We have 8 times where we have to decide if its a 1 or a 0 so that would be $2^8$. $\Box$\\
\begin{figure}[h]
\begin{center}
\includegraphics[width=0.8\textwidth]{CArules.png}
\end{center}
\caption{If you had difficulty following the proof above, here is a simple visual aid that can help. We have eight possible states of the three blocks in the top portion and then we assign an output to each of those states. This particular set is called Rule 30.}
\end{figure}
\\
Now, is there a numbering system that can give a number to each configuration? Well, yes there is. Stephen Wolfram developed the method for this. He did this by converting the binary string of the eight new boxes into decimal. First, we define $x$ to be the string of 3 digits in $\mathbb{F}_2^3$. Then, we let $f$ at $x$ be $a_k$ for $0\leq k \leq 7$. And finally we can define another function $r$ that will convert $f$ into a decimal number.\\
\begin{center}
	\begin{tabular}{ | c | c | c | c | c | c | c | c | c | }
	\hline $(x_{i-1},x_i,x_{i+1})$ & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000 \\
	\hline $f$ & $a_7$ & $a_6$ & $a_5$ & $a_4$ & $a_3$ & $a_2$ & $a_1$ & $a_0$ \\
	\hline 
	\end{tabular}
\end{center}
$$r(f)=\sum_{i=0}^7 a_i 2^i$$
That equation he found will enumerate each of the 256 Elementary rules. Let's go through an example of this enumeration though.\\
\\
\textit{Example}: What is the number for the following table?\\
\begin{center}
	\begin{tabular}{ | c | c | c | c | c | c | c | c | c | }
	\hline $(x_{i-1},x_i,x_{i+1})$ & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000 \\
	\hline $f$ & $0$ & $1$ & $1$ & $0$ & $1$ & $1$ & $1$ & $0$ \\
	\hline 
	\end{tabular}
\end{center}
For this example, all we need to do is just plug into the equation.
$$r(f)=\sum_{i=0}^7 a_i 2^i=0\times 2^7+ 1\times 2^6 + 1 \times 2^5 + 0 \times 2^4 +1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 +0 \times 2^0=110$$
And thus this is Rule 110. This rule in particular is quite famous because it is one of the well known class 4 Cellular Automata and is also known to be Turing Complete\footnote{This was discovered by Matthew Cook and published in 2004, and means that it is capable of supporting universal computation (Wikipedia [3]).}. Now, what is "class 4" and why does this even matter? Well, Elementary CA and CA in general can be classified into 4 distinct categories based on complexity (Wikipedia [2]):
\begin{enumerate}
\item Class 1: Nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears.
\item Class 2: Nearly all initial patterns evolve quickly into stable or oscillating structures. Some of the randomness in the initial pattern may filter out, but some remains. Local changes to the initial pattern tend to remain local.
\item Class 3: Nearly all initial patterns evolve in a pseudo-random or chaotic manner. Any stable structures that appear are quickly destroyed by the surrounding noise. Local changes to the initial pattern tend to spread indefinitely.
\item Class 4: Nearly all initial patterns evolve into structures that interact in complex and interesting ways, with the formation of local structures that are able to survive for long periods of time. Class 2 type stable or oscillating structures may be the eventual outcome, but the number of steps required to reach this state may be very large, even when the initial pattern is relatively simple. Local changes to the initial pattern may spread indefinitely. Wolfram has conjectured that many, if not all class 4 cellular automata are capable of universal computation. This has been proven for Rule 110 and Conway's game of Life.
\end{enumerate}
Class 4 is the meat that CA research takes part in. Strange things start to arise out of patterns that logic assumes that simple patterns will eventually occur, but none never do.\\
\\
With that stated, that is the end of these notes for this week. The next few pages will all contain a few images of rules and their visual outcomes when processed a several generations forward (Wolfram [5]).
\begin{figure}[h]
\includegraphics[width=1.25\textwidth]{ECA1.png}
\end{figure}
\begin{figure}[h]
\includegraphics[width=1.25\textwidth]{ECA2.png}
\end{figure}
\begin{thebibliography}{9}
\bibitem{Dynamical Systems} H. S. Mortveit and C. M. Reidys, \textit{An Introduction to Sequential Dynamical Systems}, Springer Science+Business Media LLC, New York, 2008.
\bibitem{Cellular Automata} \url{http://en.wikipedia.org/wiki/Cellular_automaton}. Wikipedia, January 20, 2015.
\bibitem{Rule 110} \url{http://en.wikipedia.org/wiki/Rule_110}. Wikipedia, January 20, 2015.
\bibitem{Translational Invariance} \url{http://en.wikipedia.org/wiki/Translational_symmetry}. Wikipedia, January 20, 2015.
\bibitem{A New Kind of Science} Wolfram, Stephen. \textit{A New Kind of Science}. Champaign: Wolfram Media, Inc., 2002
\end{thebibliography}
\end{document}