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

Определения

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

Клеточным автоматом (КА) [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]

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

[math]\triangleleft[/math]

Теорема:

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

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

[math]\triangleright[/math]

Пусть эмулируется ЛКА с окрестностью радиуса [math]d[/math] (из [math]2d + 1[/math] клетки). Пусть в автомате клетки всего [math]n[/math] состояний. Сопоставим каждому состоянию алфавита МТ, так что состояние покоя будет отображаться в пустую клетку ленты. Дополнительно введем символы-терминалы, указывающие на то, что соответствующие клетка ленты автоматы еще находятся в состояниях покоя. С точки зрения ЛКА клетки с терминалами будут считаться пустыми. Автомат МТ будет иметь [math]O(n^{2d+1})[/math] состояний — по состоянию для каждой возможной окрестности клетки, а также состояния, обеспечивающие правильную эмуляцию. Исходное состояние ленты МТ имеет следующий вид: отрезок, содержащий все клетки, эквивалентные неспокойным клеткам автомата, ограниченный с концов терминалами. Эмуляция каждой фазы ЛКА будет происходить следующим образом: головка будет сдвигаться до левого терминала, затем еще на [math]d[/math] влево, затем на [math]2d+1[/math] вправо, запоминая окрестность клетки, затем менять состояние текущей клетки соответственно поведению ЛКА, затем изменять окрестность, до тех пор, пока не поменяет правый терминал. При этом, если головка обрабатывает терминал, то после этого необходимо сдвинуться влево или вправо соответственно тому, какой терминал сейчас меняется, и поставить в текущую пустую клетку этот терминал. Такая МТ будет эмулировать заданный ЛКА.

[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 Cellular Automata, July 1998.