Изменения

{{Определение| id=cellularautomaton|definition='''Клеточным автоматом''' (КА) (англ. ''cellular automaton'') <tex>A</tex> размерности <tex>d</tex> называется четверка <tex> \langle {Z^d}, S, N, \delta \rangle</tex>, где

* <tex>N</tex> {{---}} конечное упорядоченное подмножество <tex>Z^d</tex>, <tex>N=\{{n_j}|\mid {n_j}=(x_{1_j}, \dots, x_{d_j}), j \in \{1 \dots n\}\}</tex>, называемое '''окрестностью''' (англ. ''neighborhood'') <tex>A</tex>. В данном определении полагается, что клетка всегда принадлежит своей окрестности.* <tex>\delta : S^{n+1} \rightarrow S</tex> {{---}} функция перехода для <tex>A</tex>.

'''Линейным клеточным автоматом''' (ЛКА) (англ. ''linear cellular automaton'') называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из <tex>2 \cdot r + 1</tex> клеток,

'''Состоянием покоя''' (англ. ''quiescent state'') называется такое состояние автомата клетки<tex>c</tex>, что если клетка автоматы клетки <tex>c</tex> и все всех ее соседи соседей (клеток из ее окрестности) находятся в состояниях покоя, то они автомат <tex>c</tex> на следующем шаге останется в них останутсятекущем состоянии.

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

'''Конфигурацией''' (англ. ''configuraton'') <tex>c_i</tex> КА называется распределение состояний автоматов по клеточному пространству, где <tex>i</tex> {{---}} шаг, после которого была получена конфигурация.

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

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

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

[[Изображение:NeighbourhoodMpneighbour.jpg|thumb|right|comment|Рис. 1. Окрестность клетки]] Каждая клетка <tex>Z_T</tex> обладает множеством <tex>Q</tex> из <tex>M = max(n + 1Каждому состоянию автомата клетки будет сопоставляться либо состояние автомата МТ, m + 1)</tex> состоянийлибо символ на ленте. Без потери общностиВсе клетки будут либо клетками ленты, будем считатьрасположенными в одном ряду, что <tex>Q = \{ 0, 1, \dots , M - 1\}</tex>, так что <tex>(i + 1)</tex> будет сопоставляться и в этом случае их состояние соответствует символу <tex>x_i</tex> машины Тьюринга при <tex>0 \le i \le m - 1</tex>на ленте МТ, а состояние либо служебными клетками. Среди служебных клеток клетка <tex>(j + 1)h</tex> будет соответствовать состоянию <tex>q_j</tex> машины Тьюринга при <tex>0 \le j \le n головке MT и в каждый момент находиться над какой- 1то клеткой ленты, клетки </tex>. Ноль является состоянием покоя <tex>Z_Ta</tex> и не будет соответствовать символам и состояниям машины Тьюринга. Окрестность построим таким образом, чтобы выделять клетку, состояние которой <tex>Q_1 \in A = \{ 1, 2, \dots, m\}b</tex> будет соответствовать символу машины Тьюринга из всегда будут указывать на клетки, состояние которой слева и справа от <tex>Q_2 \in B = \{ 1, 2, \dots, n\}h</tex> соответствует состоянию машины Тьюринга (окрестность . Остальные клетки будут находиться в таком КА показана на Рис. 1)состоянии покоя.

Таким образомЗаметим, <tex>Z_T</tex> симулирует машину Тьюрингачто это порождает следующую проблему: размер входных данных МТ конечен, используя конфигурацию, в которой оно <tex>"</tex>выглядит следовательно поддержка начальной конфигурации конечна. Так как<tex>"</tex> машина Тьюринга. Один ряд клеток МТ в <tex>Z_T</tex> представляет из себя ленту машины Тьюринга {{---}} одна клетка <tex>Z_T</tex> для каждой клетки лентыобщем случае может не остановиться, а одна клетка из соседнего ряда будет соответствовать головке МТ, и то в каждый какой-то момент времени автомат будет выглядеть так, как показано на рисунке нижеможет потребоваться расширить ленту. Клетки <tex>a</tex> и <tex>b</tex> всегда указывают на Поэтому необходимо ввести две дополнительных служебных клетки , при необходимости расширяющих ленту влево или вправо (то есть переводящих соседнюю слева и /справа от головки <tex>h</tex> соответственно. Все остальные символы используются для хранения состояний: <tex>S_k \in A</tex> обозначает клетку в свое состояние клетки ленты на расстоянии <tex>|k|</tex> от головки по направлению знака индекса, <tex>P \in B</tex> обозначает а сами переходящие в состояние головки. Клетки справа и слева от головки обозначим <tex>C_R</tex> и <tex> C_L</tex>, которые будут определять правый или левый конец использованной соответствующее пустой клетке ленты. Все клетки кроме <tex>h</tex> и клеток ленты будут находится в состоянии покоя нольМТ).

Таким образомПостроим окрестность, при симуляции головка <tex>h</tex> будет двигаться, повторяя необходимую для корректной работы такого КА. Рассмотрев поведение головки соответствующей МТи зависимости клеток КА, при этом менять состояние будут только клетки <tex>aполучим, h, b, C_Rчто минимальная по размеру окрестность имеет вид, C_L</tex>, для которых необходимо определить функции перехода. Обозначим для них функцию перехода: если <tex>x_u, q_v</tex> {{---}} символ представленный на ленте и состояние МТ, то переход будет иметь вид <tex>(x_u, q_v) = {x_p}X/q_q</tex>, где <tex>X</tex> {{---}} сдвиг влево <tex>L</tex> или вправо <tex>R</tex>. Состояния <tex>C_L</tex> и <tex>C_R</tex> необходимы для решения проблемы конца ленты: в общем случае машина Тьюринга работает с бесконечной лентой, в то время как поддержка начальной конфигурации построенного автомата конечна, и в некоторый момент пустые состояния закончатсяРис. Чтобы этого не произошло, введены <tex>C_L</tex> и <tex>C_R</tex>, которые переводят спокойные клетки в состояния, соответствующие пустым символам ленты МТ1.

[[Изображение:TapeMptape.jpg|640px|thumb|center|Рис. 2. Эмуляция ленты МТ в КА]]

[[Изображение:Transit.jpg{{Теорема|640px|thumb|center|Рис. 3. Функция перехода]] Также определим в каждой клетке состояние statement=Для произвольной <tex>w(m, n)</tex>машины Тьюринга существует линейный КА с окрестность не более, соответствующее начальному состоянию МТ. Перед началом эмуляции клетки ленты переведем в состояниячем из шести клеток, эквивалентные входным символам, клетку над самой левой непустой клеткой ленты переведем в состояние <tex>wmax(m + 1, n + 1)</tex>состояниями, которая эмулирующий эту МТ в реальном времени.|proof=Лента будет соответствовать начальному положению головкииметь следующий вид:[[Изображение:Mplintape.jpg|640px|thumb|center|Рис. 4. Тогда клетки Эмуляция ленты будут менять свои состояние так же, как лента МТв ЛКА]]Доказательство и построение автомата аналогично предыдущей теореме.

|definitionstatement=Для произвольной произвольного ЛКА можно построить эмулирующую его машину Тьюринга.|proof=Пусть эмулируется ЛКА с окрестностью радиуса <tex>d</tex>(m, из <tex>2d + 1</tex> клетки). Пусть в автомате клетки всего <tex>n)</tex> машины Тьюринга существует линейный КА с окрестность не болеесостояний. Сопоставим каждому состоянию алфавита МТ, так что состояние покоя будет отображаться в пустую клетку ленты. Дополнительно введем символы-терминалы, чем из шести клетокуказывающие на то, что соответствующие клетке ленты автоматы еще находятся в состояниях покоя. С точки зрения ЛКА клетки с терминалами будут считаться пустыми. Автомат МТ будет иметь <tex>maxO(m + 1, n ^{2d+ 1})</tex> состояниямисостояний {{---}} по состоянию для каждой возможной окрестности клетки, а также состояния, эмулирующий эту обеспечивающие правильную эмуляцию. Исходное состояние ленты МТ в реальном времени.|proof=Аналогично предыдущей теореме. Лента будет иметь имеет следующий вид:[[Изображениеотрезок, содержащий все клетки, эквивалентные неспокойным клеткам автомата, ограниченный с концов терминалами. Эмуляция каждой фазы ЛКА будет происходить следующим образом:Tape2головка будет сдвигаться до левого терминала, затем еще на <tex>d</tex> влево.jpg|640px|thumb|center|РисЗатем левый терминал будет переноситься на <tex>d</tex> клеток влево, а для каждой клетки правее нового положения левого терминала будет запоминаться ее окрестность, затем будет изменяться ее состояние соответственно поведению ЛКА. И так для всех клеток, пока не встретится правый терминал. В этом случае необходимо перенести его на <tex>d</tex> клеток вправо и продолжить менять клетки до его следующего вхождения. 2Затем перейти к следующей фазе. Эмуляция ленты Такая МТ в будет эмулировать заданный ЛКА]].