36
правок
Изменения
Нет описания правки
==Определения==
{{Определение| id=cellularautomaton|definition='''Клеточным автоматом''' (КА) (англ. ''cellular automaton'') <tex>A</tex> размерности <tex>d</tex> называется четверка <tex> \langle {Z^d}, S, N, \delta \rangle</tex>, где
* <tex>S</tex> {{---}} конечное множество, элементы которого являются состояниями <tex>A</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>.
}}
{{Определение|definition=
'''Линейным клеточным автоматом''' (ЛКА) (англ. ''linear cellular automaton'') называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из <tex>2 \cdot r + 1</tex> клеток,
находящихся на расстоянии не более <tex>r</tex> от данной.
}}
{{Определение|definition=
'''Состоянием покоя''' (англ. ''quiescent state'') называется такое состояние автомата клетки <tex>q_0c</tex>, что если автомат перешел в состояние автоматы клетки <tex>q_0c</tex>и всех ее соседей (клеток из ее окрестности) находятся в состояниях покоя, то на следующем шаге он также будет находиться в состоянии автомат <tex>q_0c</tex>на следующем шаге останется в текущем состоянии.
}}
{{Определение|definition=
'''Спокойной клеткой''' (англ. ''quiescent cell'') назовем клетку, автомат в которой перешел в состояние покоя.
}}
{{Определение|definition=
'''Конфигурацией''' (англ. ''configuraton'') <tex>c_i</tex> КА называется распределение состояний автоматов по клеточному пространству, где <tex>i</tex>{{--- }} шаг, после которого была получена конфигурация. Начальная конфиграция{{---}} <tex>c_0</tex>.
}}
{{Определение|definition=
'''Поддержкой''' (англ. ''support'') конфигурации <tex>c</tex> называется множество неспокойных клеток в ней. Обозначается <tex>sup(c)</tex>.
}}
==Другое определение линейного клеточного автомата==
вектор из состояний автоматов в клетках с <tex>i - r</tex> по <tex>i + r</tex> включительно.
}}
{{УтверждениеЛемма
|statement=Для любого ЛКА можно построить эквивалентный ему ЛКА, во всех клетках которого будет записан один и тот же автомат.
|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>.
}}
==Эквивалентность линейного клеточного автомата машине Тьюринга==
{{ЛеммаТеорема
|statement=
Для произвольной <tex>(m, n) </tex> машины Тьюринга <tex>T</tex> существует двумерный КА с окрестностью из семи клеток и клеточным пространством <tex>Z_T</tex> с <tex>max(n + 1, m + 1)</tex> состояниями, симулирующий ее в реальном времени.
|proof=
Также определим в каждой клетке состояние <tex>***w</tex>, соответствующее начальному состоянию МТ. Перед началом эмуляции клетки ленты переведем в состояния эквивалентные входным символам, клетку над самой левой непустой клеткой ленты переведем в состояние <tex>w</tex>, которая будет соответствовать начальному положению головки. Тогда клетки ленты будут менять свои состояние так же, как лента МТ.}}
{{Теорема
|statement=Для произвольной <tex>(m, n)</tex> машины Тьюринга существует линейный КА с окрестность не более, чем из шести клеток, <tex>max(m + 1, n + 1)</tex> состояниями, эмулирующий эту МТ в реальном времени.
|proof=Лента будет иметь следующий вид:
[[Изображение:Mplintape.jpg|640px|thumb|center|Рис. 4. Эмуляция ленты МТ в ЛКА]]
Доказательство и построение автомата аналогично предыдущей теореме.
}}
}}
Из доказанных выше теорем следует, что линейный клеточный автомат и машина Тьюринга эквивалентны.
==См. также ==
* [[Машина Тьюринга]]
* [[Линейный ограниченный автомат]]
== Источники информации ==
* ''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.
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]