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

Определения

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

Клеточным автоматом (КА) [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) называется такое состояние клетки, что если клетка и все ее соседи находятся в состояниях покоя, то они в них останутся.

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

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

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

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

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

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

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

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

Линейным клеточным автоматом [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]a[/math] и [math]b[/math] всегда указывают на клетки слева и справа от головки [math]h[/math] соответственно. Все остальные символы используются для хранения состояний: [math]S_k \in A[/math] обозначает состояние клетки ленты на расстоянии [math]|k|[/math] от головки по направлению знака индекса, [math]P \in B[/math] обозначает состояние головки. Клетки справа и слева от головки обозначим [math]C_R[/math] и [math] C_L[/math], которые будут определять правый или левый конец использованной ленты. Все клетки кроме [math]h[/math] и клеток ленты будут находится в состоянии покоя ноль. Таким образом, при симуляции головка [math]h[/math] будет двигаться, повторяя поведение головки соответствующей МТ, при этом менять состояние будут только клетки [math]a, h, b, C_R, C_L[/math], для которых необходимо определить функции перехода. Обозначим для них функцию перехода: если [math]x_u, q_v[/math] — символ на ленте и состояние МТ, то переход будет иметь вид [math](x_u, q_v) = {x_p}X/q_q[/math], где [math]X[/math] — сдвиг влево [math]L[/math] или вправо [math]R[/math]. Состояния [math]C_L[/math] и [math]C_R[/math] необходимы для решения проблемы конца ленты: в общем случае машина Тьюринга работает с бесконечной лентой, в то время как поддержка начальной конфигурации построенного автомата конечна, и в некоторый момент пустые состояния закончатся. Чтобы этого не произошло, введены [math]C_L[/math] и [math]C_R[/math], которые переводят спокойные клетки в состояния, соответствующие пустым символам ленты МТ. Рис. 2. Эмуляция ленты МТ в КА Функция перехода имеет следующий вид: Рис. 3. Функция перехода Также определим в каждой клетке состояние [math]w[/math], соответствующее начальному состоянию МТ. Перед началом эмуляции клетки ленты переведем в состояния, эквивалентные входным символам, клетку над самой левой непустой клеткой ленты переведем в состояние [math]w[/math], которая будет соответствовать начальному положению головки. Тогда клетки ленты будут менять свои состояние так же, как лента МТ.

[math]\triangleleft[/math]

Теорема:

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

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

[math]\triangleright[/math]

Лента будет иметь следующий вид: Рис. 2. Эмуляция ленты МТ в ЛКА Доказательство аналогично предыдущей теореме.

[math]\triangleleft[/math]

Теорема:

Для произвольного ЛКА можно построить эмулирующую его машину Тьюринга.

Из доказанных выше теорем следует, что линейный клеточный автомат и машина Тьюринга эквивалентны.

Литература

• A.R. Smith III, Simple Computation-Universal Cellular Spaces, Journal of Association for Computing Machinery, Vol. 18, No. 3, July 1971.
• M. Delorme, An Introduction to CellularAutomata, July 1998.