Просмотр исходного текста страницы Линейный клеточный автомат, эквивалентность МТ

==Определения==
{{Определение|definition=
'''Клеточным автоматом''' (КА) <tex>A</tex> размерности <tex>d</tex> называется четверка <tex><{Z^d}, S, N, \delta></tex>, где
* <tex>S</tex> {{---}} конечное множество, элементы которого являются состояниями <tex>A</tex>.
* <tex>N</tex> {{---}} конечное упорядоченное подмножество <tex>Z^d</tex>, <tex>N=\{{n_j}|{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=
'''Линейным клеточным автоматом''' (ЛКА) называется одномерный клеточный автомат, окрестность каждой клетки которого состоит из <tex>2 \cdot r + 1</tex> клеток,
находящихся на расстоянии не более <tex>r</tex> от данной.
}}

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

{{Определение|definition=
Конфигурация называется '''пассивной''' (passive), если <tex>c = sup(c)</tex>.
}}

{{Определение|definition=
Конфигурации называются '''непересекающимися''' (disjoint), если их поддержки не пересекаются как множества.
}}


==Другое определение линейного клеточного автомата==
{{Определение|definition=
'''Линейным клеточным автоматом''' <tex>A</tex> назовем бесконечную ленту, в каждой клетке которой записан некоторый автомат. На вход автомату в клетке <tex>i</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= 
}}