A Study and Comparison of First and Second Order Cellular Automata with Examples

Abstract

This thesis will give an introduction to the concepts of cellular automata and higher order cellular automata, and go through several examples of both. Cellular automata are discrete systems of cells in an n-dimensional grid. The cells interact with each other through the use of a rule depending only on local characteristics, which lead to some global behaviour. Higher order cellular automata are hierarchical structures of cellular automata with added possibilities for dynamic local interaction. We first give an introduction for non-mathematicians. A mathematical definition of cellular automata follows, and we illustrate the many possibilities with a few examples. Higher order cellular automata are introduced and defined, and we look at the consequences higher order cellular automata has on optimization of computer implementations. Finally we apply higher order structures to some of the examples, and study the effects.