Random Explorations in Automata Theory
Gary J. Shannon
Created: Mar. 2, 2003
Last Updated: Mar. 9, 2003

Some Definitions

AUTOMATON - In these pages we explore two kinds of automata; cellular automata and matrix automata.  See Automata Defined for more details.

BEAD RACER - A particular cellular automaton designed specifically to emulate electronic logic circuits. See Bead Racer for more details.

CELL - A cell is one unit of a space filling grid that can contain two or more states.

CLOCK - Normally every cell in a cellular automaton or node in a matrix automaton is updated simulataneously at the tick of a master clock that controls the speed at which the automaton changes. See Automaton Clocks for more details.

GAME OF LIFE - This is a 2-dimensional cellular automaton with a particular set of rules discovered by John Conway. See What is the Game of Life for more details.

LINK - In a matrix automaton nodes are connected to each other by links.  These links explicity define the neighborhood of the node.

MATRIX - A matrix is a configuration of nodes and links that is differes from a space filling grid. See Matrix Automata for more detailed information. 

MOORE NEIGHBORHOOD - A neighborhood defined in a square-celled automaton grid in which each cell is able to see both its four orthagonal neighbors as well as its four diagonal neighbors. See Cellular Neighborhoods for more details.

NEIGHBORHOOD - In a cellular automaton the neighbor is the set of nearby cells that will participate in the computation of the next state of a cell.  In a matrix automaton the neighborhood is the set of nodes to which a given node is linked. See Cellular Neighborhoods for more details.

NODE - A node is the equivalent of a cell in a Matrix Automaton.

PHOTON - Any small configuration of cells that moves across the grid at the speed of light.

RULE - A rule is a set of intructions that specifiy which state each cell or node will take in the next tick based on the states of the other cells in the neighborhood.  See Automata Defined for more details.

SPACE FILLING GRID - When space is divided into cells in such a way that the entire space is filled with cells then the resulting grid is a space filling grid.  See Examples of Space Filling Grids for more information.

SPEED OF LIGHT - The fastest speed at which any configuration of cells can move across the grid.  It is equal to 1 cell per tick.

STATE - A cell in a cellular automaton or a node in a matrix automaton can contain a number which is called the state of that cell or node.  When displaying an automaton graphically states are usually represented by different colors.

SYNCHRONOUS - When every cell in an automaton is updated simultaneously as governed by a master clock then the automaton is called synchronous.  Other types of automata include asynchronous, phase-synchoronous, coupled asynchronous and sequential. See Automaton Clocks for more details.

TUBE - An automaton formed by roling a very narrow grid into a thin tubular shape. See Tubular and Tubular Toroidal Automata for more information.

== UNDER CONSTRUCTION. Much more to follow ==