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:
·
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
·
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
Online
canned book – Theory of Self-reproducing Automata
o
Google Code – Rule Table
Repository
o
Golly CA Simulation Environment