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

Определения

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

Клеточным автоматом (КА) [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], называемое окрестностью (neighborhood) [math]A[/math]. [math]\delta : S^{n+1} \rightarrow S[/math] — функция перехода для [math]A[/math].

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

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

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

Состоянием покоя (quiescent state) называется такое состояние автомата [math]q_0[/math], что если автомат перешел в состояние [math]q_0[/math], то на следующем шаге он также будет находиться в состоянии [math]q_0[/math].

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

Спокойной клеткой (quiescent cell) назовем клетку, автомат в которой перешел в состояние покоя.

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

Конфигурацией (configuraton) [math]c_i[/math] КА называется распределение состояний автоматов по клеточному пространству, где [math]i[/math]--- шаг, после которого была получена конфигурация. Начальная конфиграция---[math]c_0[/math].

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

Поддержкой (support) конфигурации [math]c[/math] называется множество спокойных клеток в ней. Обозначается [math]sup(c)[/math].

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

Конфигурация называется пассивной (passive), если [math]c = sup(c)[/math].

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

Конфигурации называются непересекающимися (disjoint), если их поддержки не пересекаются как множества.

Другое определение линейного клеточного автомата

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

Линейным клеточным автоматом [math]A[/math] назовем бесконечную ленту, в каждой клетке которой записан некоторый автомат. На вход автомату в клетке [math]i[/math] подается вектор из состояний автоматов в клетках с [math]i - r[/math] по [math]i + r[/math] включительно.

Утверждение:

Для любого ЛКА можно построить эквивалентный ему ЛКА, во всех клетках которого будет записан один и тот же автомат.

[math]\triangleright[/math]

Так как окрестность каждой клетки конечна и размер автомата в клетке конечен, то всего существует конечное число автоматов. Обозначим их множество как [math]D[/math]. Построим автомат [math]B[/math] следующим образом: множеством вершин [math]B[/math] будет объединение множеств вершин автоматов из [math]D[/math], переходы между вершинами [math]u[/math] и [math]v[/math] будет совпадать с переходами [math]D_i[/math], если [math]u[/math] и [math]v[/math] соответствуют вершинам из [math]D_i[/math], иначе переход отсутствует. Начальным состоянием автомата будет состояние,соответствующее начальному состоянию автомата [math]D_k[/math], который был записан в текущей клетке. Очевидно, что поведение такого автомата будет совпадать с поведением [math]D_k[/math].

[math]\triangleleft[/math]

Эквивалентность линейного клеточного автомата машине Тьюринга

Лемма: