Computing with Cellular Automata – Nicholas Shellabarger


          This document serves as a write-up of the concerning topic which I will present to our class at a further time. It also will serve as an outline directing the professor to which order the topic will be presented. Note, in the place where the author would like to comment related or unrelated to the topic at hand REM will be placed before each comment denoting that the subsequent text may or may not be considered in the actual presentation. The contents of this document are proposed to fit within a 10 minute time period, leaving 2 addition minutes for question. Cheers.


REM  What color is Microsoft? (Hint: Microsoft Works)

Writing the write-up:

          Initially, when beginning to write my write-up it was not clear to me what a write-up was due to the fact that you can also write-up a write-up. In context, it must mean that I give my presentation in written form, with exclusion of all the hand waving that will take place during the oral presentation. Hence, I am to write an outline of the presentation, listing the topics in the order which they will be presented. It’s an outline. So, jumping to the requirements of the actual presentation before returning to focus, the presentation should be interesting and informative. Reading the sentence that followed, I would like to add illustrative, based on the fact that having examples might be a plus.


Terms that may or may not show up in the discussion:

·       Tyranny of Numbers

·       Maxwell’s chair

·       Role of science

Note, please keep in mind that the sole purpose of the above is to provide the presenter a creative framework in which at his/her discretion the following will be organized in a presentable format for the intended audience.


General order of discussion:

·       Background Information

o   What is Cellular Automata (CA)?

§  Motivation

·       Von Neumann’s work in the modeling of cell biology

§  Familiar faces of CA

·       Game Of Life

·       Von Neumann’s Neighborhood

o   How are CAs relating to computing?

§  Brief discussion about various models of computation     REM Leads into next discussion

·       Foundation : Turing VS Church

·       Relation between CAs and Turing

o   Turing is a 1-dimensional CA

·       A hint of Computation Theory (Universal Computation)

o   Basic principle: If you can do it on a Turing Machine, then you can certainly do it on a modern day computer. Note, the converse also holds.

§  A Turing Machine is a first order CA, so the same holds for CAs as well.


·       Relation To System Architecture

o   Serial VS Parallel Architectures

§  Turing is serial

§  CAs exhibits parallel characteristics

·       Problems done in lower order CAs can also be done in higher order CAs with equal to or greater efficiency.

·       Problem: As the order of the CA increases so does its complexity.

o   Serial to Parallel is ‘hard’

o   Quote regarding the progression of CPUs


·       Potential Demos

o   Game of Life, for those unfamiliar with the program

o   Sierpinksi Triangle (2 degrees of freedom)

o   Sierpinksi (3 degrees of freedom)

o   Sierpinksi (4 degrees of freedom)

o   Sierpinksi ( ( n > 4 ) degrees of freedom | where n is an integer )

§  Don’t know yet.

o   Turing next-subset algorithm

§  Adding 1 to an n digit binary number, where n is the cardinality of the super-set

o   Applications in Checkers

§  Checkers next-move calculator (1)

·       Given the state of a board computes the moves available for player

§  Checker mass spatial composition mapping (2)

·       Given the state of a checkers board decompose the board into contiguous bodies of the same type of piece

o   For example, taking the case of the initial state of the board, there are is 1 contiguous body of pieces for each player.

§  Checkers piece collision checking (3)

·       Show potential areas of the board that will result in someone losing a piece

Note, (1), (2), and (3) happen in sequence, meaning that they are derived in sequence in the same CA space.

o   Self-reproducing Loops (SRCA)

§  Langton’s Loop


·       Further Resources

o   Cellular Automata - Wiki Page

o   Langton's Loop - Wiki Page

o   Online canned book – Theory of Self-reproducing Automata

o   SRCA Java Applet

o   Google Code – Rule Table Repository

o   Golly CA Simulation Environment