1 of 16

Game of CompArch

cellular automata and computing

2 of 16

What are Cellular Automata?

Systems of cells that evolve through discrete time steps according to a set of rules. Behavior can only be dictated by a cell’s neighbors, and all rules must be able to be described mathematically.

https://upload.wikimedia.org/wikipedia/commons/e/e5/Gospers_glider_gun.gif

3 of 16

+

Wolfram’s Rule 30

http://mathworld.wolfram.com/ElementaryCellularAutomaton.html

4 of 16

Applications

Modelling discrete dynamic systems and visualizing complex patterns

5 of 16

Coral Growth

One set of rules shows nutrients moving through water, while another models coral growth as a “seed” interacts with these nutrients.

http://www.calcifer.org/kenneth-christiansen/ComputerScience/2d-coral-growth-2.pdf

6 of 16

Describing Cellular Automata

Can be compared to a state-based model

The Halting Problem

The Edge of Chaos

Cellular automata lend themselves to a state-based mathematical description. For a given timestep, you have the Lattice, or the surface the automata acts on, States, a mapping of the current behavior of each cell onto the lattice (for example, this can involve assigning integer categories to the color of each individual cell), Neighbors, or a characterization of the neighbors of each cell (the two most common neighborhoods are the Van Neumann neighborhood which considers all of the cells orthogonal to a given cell, and the Moore neighborhood, which considers all of the cells surrounding a particular cell), and a Transition Function which maps a new set of states onto the lattice based on the previous conditions and neighbors.

This leads to a lot of interesting behaviors - generally, there are four main classes of cellular automata. Class 1 describes models that converge to one state, Class 2 describes models that display constant or perioidic behavior, Class 3 describes models that display completely random behavior, and Class 4 describes models that display complex patterns and emergent behavior. In general, we care the most about Class 4 models : these have been shown to be Turing complete.

Because of this, they are inherently unpredictable : the halting problem explores this question by asking whether a programmed machine can predict whether or not given input program will terminate, which can always be proved wrong by counter example for class 4 systems. Because they are so unpredictable, these models lie on the edge of chaos - their behavior is neither completely random nor completely deterministic.

7 of 16

A Turing Machine Has...

Finite internal states

Infinite external data storage

A program specified by finite instructions in a predefined language

Self-reference

8 of 16

The Game of Life

https://en.wikipedia.org/wiki/File:Conways_game_of_life_breeder_animation.gif

9 of 16

Rules:

Survival: an “alive” cell remains alive if two or three of its neighbors are alive

Birth: a “dead” cell becomes alive if exactly three of its neighbors are alive

Death: an alive cell dies if fewer than two or more than three of its neighbors are alive

10 of 16

A community has built itself around the Game of Life, finding stable patterns that can be used for various purposes.

https://mathblog.com/the-game-of-life-in-octave/

Oscillator

Glider

Pulser

11 of 16

AND

OR

NOT

12 of 16

AND

OR

NOT

INPUTS

OUTPUT

INPUTS

OUTPUT

INPUT

13 of 16

http://archive.li/obdP1

The first Game of Life Turing machine ever constructed.

14 of 16

Our Inspiration For This Project

CPU In The Game Of Life

15 of 16

Not as efficient when compared to using building blocks like transistors to perform the same tasks, but an interesting concept that a “universe” built on four simple rules can lead to infinitely large computational power.

Our Adder

And we’ve implemented an adder in the Game of Life! Traditional computer architectures are pretty inefficient in the Game of Life because logic gates take a large amount of space (when compared to using transistors to perform the same tasks) and need large amounts of time steps to resolve any propagation delays. However, it is a fun thought exercise that such simple rules can lead to infinitely large computational power.

Our Adder

-One of the building blocks of our original ALU

-Performance Analysis

--Hard to directly compare this model to a transistor based adder.

--Because these two methods of computation exist in universes with largely different rule sets.

The system becomes pretty inefficient when trying to bring logic level design.

--However, this project was a fun though exercise that

Proved simple rules can lead to infinitely large computational power. It also turns out the game of life

Is a great visual aid for comparing the propogation delay, area trade-offs, and other computer architecture variables

That we would formerly compute by han.

16 of 16

Questions, Comments, Concerns?