# M.S. Project – Functional Analysis of Cellular Automata

This project was prepared to satisfy the thesis requirement for the Master of Science degree. In this project, an evolutionary algorithm is used to infer the transition function for a generalized model of a two dimensional binary cellular automata.

### Documents

M.S. Project Presentation (pdf export of presentation, 69 pages)

M.S. Project Report (pdf, 55 pages)

# Abstract

Cellular automata are systems that consist of a number of homogenous sub-systems

(referred to as cells). Cellular automata models are used in many different disciplines

and are capable of exhibiting many different types of physical, biological, or

information-theoretic behaviors. Within a cellular automaton, each cell is associated

with a particular state. A new generation of cells are created according to some

fixed transition rule, where the next state of a cell is determined based on the state

history of some set of cells in the system (referred to as that cell’s neighborhood).

For determinate systems, the state progression of a cellular automata is uniquely

determined by its initial state, neighborhood function, and transition function. Given

only the neighborhood function of a determinate cellular automaton, one can infer

its transition function by observing the state transitions that take place and building

a lookup table that defines the transition function. However, given only observations

of the state transitions, it is difficult to infer the neighborhood function that governs

the cellular automaton. This project implements a discrete event specification model

of a general cellular automaton, uses this simulation to generate a number of different

state transition trajectories, and uses an evolutionary algorithm to search the space

of possible neighborhood functions in order to find the neighborhood function that

was originally used to generate the trajectories. Results are presented that show

the intelligent search algorithm is significantly more efficient than brute force search

under most circumstances.

## Like us on facebook!

## Recent Posts

- Fujitsu Artificial Market Segmentation (or, how to make a Mac ScanSnap FI-5110EOXM work in Windows 8.1)
- MATLAB: Easily perform large batch jobs on multiple machines (without MATLAB Distributed Computing Server)
- Using PS to output human readable memory usage for each process using AWK
- Building SOAP services on Google App Engine in Java: Part 1 – The Servlet
- Eclipse RCP: Setting P2 repositories (update sites) programmatically (for when p2.inf fails).