Tutorial on Cellular Automata

摘要

This tutorial surveys computational aspects of cellular automata, a discrete dynamical model introduced by S. Ulam and J. von Neumann in the late 40s: a regular grid of finite state cells evolving synchronously according to a common local rule described by a finite automaton. Formally, a cellular automaton is a tuple (d, S, N, f) where d ∈ N is the dimension of the cellular space, S is the finite set of states, N (is contained in)_(finite) Z~d is the finite neighborhood and f: S~N → S is the local rule of the cellular automaton.