Cellular Automata/Formalization

Formalization sometimes seems an unneeded burden when learning something new, yet it is the main tool to pass scientific knowledge to others. An informal introduction into CA was already presented, now is time for a detailed formalization that will allow us to dig further into the theory of CA.

Overview

This book tries to mix rigorous mathematical formulae with self explanatory graphical representations of the same equations.

The formalization chapter is composed of the following sections:

1. The mathematical model focuses on a general definition of one-dimensional cellular automata. At the end, it generalizes the theory to more than one dimension and functions that look more than one step into history.
2. A neighborhood can be defined with general equations or can be described with a less general graphical definition. This chapter focuses on the last approach to describe the most common CA.
3. A rule is a common way to define transition functions, some common ways to define a rule are described here.
4. A pattern is used to describe a part of the content of a cellular automaton. Since some CA have been studied in detail, some patterns have been observed frequently as well. This section describes common methods for describing patterns.

Common nomenclature

A common nomenclature lookup table is provided here.

Abbreviations:

CA	cellular automata

Basic symbols:

$S$	set of cell states
$k$	number of cell states in S ($k=|S|$)
$c$	cell state (value) ($c\in S$)
$\alpha$, $\beta$	strings of cell values
$C$	configuration (might be finite or infinite)
$N$	finite configuration length
$x$	position index
$A$	neighborhood definition as a set of neighbors
$r$	neighborhood radius
$n$	neighborhood specific value or link in the preimage network
$o$	overlap specific value or node in the preimage network
$f$	local transition function
$F$	global transition function
$t$	time index or identifies the present

Preimage model related symbols:

$D$	preimage matrix
$d$	elements of $D$
$b$	preimage vector
$b_{\mathrm {L} }$	left boundary vector
$b_{\mathrm {R} }$	right boundary vector
$b_{\mathrm {u} }$	unrestricted boundary vector
$p$	number of preimages
$w_{n}$	link (neighborhood) weight
$w_{o}$	node (overlap) weight