Изменения

{{Определение| 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>q_0c</tex>, что если автомат перешел в состояние автоматы клетки <tex>q_0c</tex>и всех ее соседей (клеток из ее окрестности) находятся в состояниях покоя, то на следующем шаге он также будет находиться в состоянии автомат <tex>q_0c</tex>на следующем шаге останется в текущем состоянии.

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

'''Конфигурацией''' (англ. ''configuraton'') <tex>c_i</tex> КА называется распределение состояний автоматов по клеточному пространству, где <tex>i</tex>{{--- }} шаг, после которого была получена конфигурация. Начальная конфиграция{{---}} <tex>c_0</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_Th</tex> обладает множеством будет соответствовать головке MT и в каждый момент находиться над какой-то клеткой ленты, клетки <tex>Qa</tex> из и <tex>M = max(n + 1, m + 1)b</tex> состояний. Без потери общности, будем считать, что всегда будут указывать на клетки слева и справа от <tex>Q = \{ 0, 1, \dots , M - 1\}h</tex>. Остальные клетки будут находиться в состоянии покоя.  Заметим, так что <tex>это порождает следующую проблему: размер входных данных МТ конечен, следовательно поддержка начальной конфигурации конечна. Так как МТ в общем случае может не остановиться, то в какой-то момент может потребоваться расширить ленту. Поэтому необходимо ввести две дополнительных служебных клетки, при необходимости расширяющих ленту влево или вправо (i + 1)<то есть переводящих соседнюю слева/tex> будет сопоставляться символу <tex>x_i</tex> машины Тьюринга при <tex>0 \le i \le m - 1</tex>справа клетку в свое состояние, а сами переходящие в состояние, соответствующее пустой клетке ленты МТ).  Построим окрестность, необходимую для корректной работы такого КА. Рассмотрев поведение МТ и зависимости клеток КА, получим, что минимальная по размеру окрестность имеет вид, представленный на Рис. 1. [[Изображение:Mptape.jpg|640px|thumb|center|Рис. 2. Эмуляция ленты МТ в КА]] Также определим в каждой клетке состояние <tex>(j + 1)w</tex> будет соответствовать , соответствующее начальному состоянию <tex>q_j</tex> машины Тьюринга при <tex>0 \le j \le n - 1</tex>МТ. Ноль является состоянием покоя Перед началом эмуляции клетки ленты переведем в состояния эквивалентные входным символам, клетку над самой левой непустой клеткой ленты переведем в состояние <tex>Z_Tw</tex> и не , которая будет соответствовать символам и состояниям машины Тьюринганачальному положению головки. Окрестность построим таким образомТогда клетки ленты будут менять свои состояние так же, чтобы выделять клетку, состояние которой как лента МТ.}} {{Теорема|statement=Для произвольной <tex>Q_1 \in A = \{ 1(m, 2, \dots, m\}n)</tex> будет соответствовать символу машины Тьюринга существует линейный КА с окрестность не более, чем из клеткишести клеток, состояние которой <tex>Q_2 \in B = \{ max(m + 1, 2, \dots, n\}+ 1)</tex> соответствует состоянию машины Тьюринга (окрестность клетки состояниями, эмулирующий эту МТ в таком КА показана на реальном времени.|proof=Лента будет иметь следующий вид:[[Изображение:Mplintape.jpg|640px|thumb|center|Рис. 1)4. Эмуляция ленты МТ в ЛКА]]Доказательство и построение автомата аналогично предыдущей теореме. }}

Таким образом, {{Теорема|statement=Для произвольного ЛКА можно построить эмулирующую его машину Тьюринга.|proof=Пусть эмулируется ЛКА с окрестностью радиуса <tex>Z_Td</tex> симулирует машину Тьюринга, используя конфигурацию, в которой оно (из <tex>"2d + 1</tex>выглядит какклетки). Пусть в автомате клетки всего <tex>"n</tex> машина Тьюрингасостояний. Сопоставим каждому состоянию алфавита МТ, так что состояние покоя будет отображаться в пустую клетку ленты. Один ряд клеток Дополнительно введем символы-терминалы, указывающие на то, что соответствующие клетке ленты автоматы еще находятся в состояниях покоя. С точки зрения ЛКА клетки с терминалами будут считаться пустыми. Автомат МТ будет иметь <tex>Z_TO(n^{2d+1})</tex> представляет из себя ленту машины Тьюринга состояний {{--- одна клетка }} по состоянию для каждой возможной окрестности клетки, а также состояния, обеспечивающие правильную эмуляцию. Исходное состояние ленты МТ имеет следующий вид: отрезок, содержащий все клетки, эквивалентные неспокойным клеткам автомата, ограниченный с концов терминалами. Эмуляция каждой фазы ЛКА будет происходить следующим образом: головка будет сдвигаться до левого терминала, затем еще на <tex>Z_Td</tex> влево. Затем левый терминал будет переноситься на <tex>d</tex> клеток влево, а для каждой клетки лентыправее нового положения левого терминала будет запоминаться ее окрестность, а одна клетка из соседнего ряда затем будет соответствовать головке изменяться ее состояние соответственно поведению ЛКА. И так для всех клеток, пока не встретится правый терминал. В этом случае необходимо перенести его на <tex>d</tex> клеток вправо и продолжить менять клетки до его следующего вхождения. Затем перейти к следующей фазе. Такая МТбудет эмулировать заданный ЛКА.

Из доказанных выше теорем следует, что линейный клеточный автомат и машина Тьюринга эквивалентны. ==См. также ==* [[Машина Тьюринга]]* [[Изображение:TapeЛинейный ограниченный автомат]] == Источники информации ==* ''A.R. Smith III'' {{---}} '''Simple Computation-Universal Cellular Spaces''', Journal of Association for Computing Machinery, Vol. 18, No. 3, July 1971.jpg|640px|thumb|center|Рис* ''M. 2Delorme'' {{---}} '''An Introduction to Cellular Automata''', July 1998. Эмуляция ленты МТ в КА [[Категория: Теория вычислимости]][[Категория: Вычислительные формализмы]]