Изменения
Нет описания правки
==Определения==
{{Определение|definition=
'''Клеточным автоматом''' (КА) <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}|{n_j}=(x_{1_j}, \dots, x_{d_j}), j \in \{1 \dots n\}\}</tex>, называемое '''окрестностью''' (''neighborhood'') <tex>A</tex>.
==Эквивалентность линейного клеточного автомата машине Тьюринга==
{{Лемма
|statement= Для произвольной (m, n) машины Тьюринга <tex>T</tex> существует двумерный КА с окрестностью из семи клеток и клеточным пространством <tex>Z_T</tex> с <tex>max(n + 1, m + 1)</tex> состояниями, симулирующий ее в реальном времени.|proof=Каждая клетка <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)</tex> будет соответствовать состоянию <tex>q_j</tex> машины Тьюринга при <tex>0 \le j \le n - 1</tex>. Ноль является состоянием покоя <tex>Z_T</tex> и не будет соответствовать символам и состояниям машины Тьюринга. Окрестность построим таким образом, чтобы выделять клетку, состояние которой <tex>Q_1 \in A = \{ 1, 2, \dots, m\}</tex> будет соответствовать символу машины Тьюринга из клетки, состояние которой <tex>Q_2 \in B = \{ 1, 2, \dots, n\}</tex> соответствует состоянию машины Тьюринга. В частности, подходит такая окрестность: здесь будет нормальная картинка <tex>\_*\_</tex> <tex>*X*</tex> <tex>***</tex> Таким образом, <tex>Z_T</tex> симулирует машину Тьюринга, используя конфигурацию, в которой оно <tex>"</tex>выглядит как<tex>"</tex> машина Тьюринга. Один ряд клеток в <tex>Z_T</tex> представляет из себя ленту машины Тьюринга - одна клетка <tex>Z_T</tex> для каждой клетки ленты, а одна клетка из соседнего ряда будет соответствовать головке МТ.
}}
