Линейный клеточный автомат, эквивалентность МТ

Определения

Определение:

Клеточным автоматом [math]A[/math] размерности [math]d[/math] называется четверка [math]\lt {Z^d}, S, N, \delta\gt [/math], где [math]S[/math] --- конечное мнжество, элементы которого являются состояниями [math]A[/math]. [math]N[/math] --- конечное упорядоченное подмножество [math]Z^d[/math], [math]N=\{{n_j}|{n_j}=(x_{1_j}, \dots, x_{d_j}), j \in \{1 \dots n\}\}[/math], называемое окрестностью [math]A[/math]. [math]\delta : S^{n+1} \rightarrow S[/math] --- функция перехода для [math]A[/math].

Определение:

Линейным клеточным автоматом называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из [math]2 \cdot r + 1[/math] клеток, находящихся на расстоянии не более [math]r[/math].