105
правок
Изменения
Нет описания правки
}}
{{Определение|definition=
'''Конфигурацией''' (configuraton) <tex>c_i</tex> КА называется распределение состояний автоматов по клеточному пространству, где <tex>i</tex>{{--- }} шаг, после которого была получена конфигурация. Начальная конфиграция{{---}} <tex>c_0</tex>.
}}
{{Определение|definition=
[[Изображение:Neighbourhood.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)</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> соответствует состоянию машины Тьюринга (окрестность клетки в таком КА показана на Рис. 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>, которые переводят спокойные клетки в состояния, соответствующие пустым символам ленты МТ.
}}
