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

Определения

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

Клеточным автоматом (КА) [math]A[/math] размерности [math]d[/math] называется четверка [math] \langle {Z^d}, S, N, \delta \rangle[/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]

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

Лемма:

Для произвольной (m, n) машины Тьюринга [math]T[/math] существует двумерный КА с окрестностью из семи клеток и клеточным пространством [math]Z_T[/math] с [math]max(n + 1, m + 1)[/math] состояниями, симулирующий ее в реальном времени.

Доказательство:

[math]\triangleright[/math]

Рис. 1. Окрестность клетки Каждая клетка [math]Z_T[/math] обладает множеством [math]Q[/math] из [math]M = max(n + 1, m + 1)[/math] состояний. Без потери общности, будем считать, что [math]Q = \{ 0, 1, \dots , M - 1\}[/math], так что [math](i + 1)[/math] будет сопоставляться символу [math]x_i[/math] машины Тьюринга при [math]0 \le i \le m - 1[/math], а состояние [math](j + 1)[/math] будет соответствовать состоянию [math]q_j[/math] машины Тьюринга при [math]0 \le j \le n - 1[/math]. Ноль является состоянием покоя [math]Z_T[/math] и не будет соответствовать символам и состояниям машины Тьюринга. Окрестность построим таким образом, чтобы выделять клетку, состояние которой [math]Q_1 \in A = \{ 1, 2, \dots, m\}[/math] будет соответствовать символу машины Тьюринга из клетки, состояние которой [math]Q_2 \in B = \{ 1, 2, \dots, n\}[/math] соответствует состоянию машины Тьюринга (окрестность клетки в таком КА показана на Рис. 1). Таким образом, [math]Z_T[/math] симулирует машину Тьюринга, используя конфигурацию, в которой оно [math]"[/math]выглядит как[math]"[/math] машина Тьюринга. Один ряд клеток в [math]Z_T[/math] представляет из себя ленту машины Тьюринга - одна клетка [math]Z_T[/math] для каждой клетки ленты, а одна клетка из соседнего ряда будет соответствовать головке МТ.

[math]\triangleleft[/math]

Рис. 2. Эмуляция ленты МТ в КА