Основные определения
Рассматриваемая в этом разделе модель алгоритмов была предложена английским математиком Тьюрингом в 1937г. еще до создания современных компьютеров компьютеров1)
Он исходил из общей идеи моделирования работы вычислителя, оперирующего в соответствии с некоторым строгим предписанием. В машине Тьюринга расчленение процесса вычисления на элементарные шаги доведено в известном смысле до предела. Элементарным действием является замена одного символа в ячейке на другой и перемещение к соседней ячейке. При таком подходе процесс вычисления значительно удлиняется, но зато логическая структура процесса сильно упрощается и приобретает удобный для теоретического исследования вид.
Машина Тьюринга (м.Т.) состоит из неограниченной в обе стороны ленты, разбитой на ячейки, по которой передвигается головка машины. Такая "бесконечность" ленты является математической абстракцией, отражающей потенциальную неограниченность памяти вычислителя. Разумеется, в каждом завершающемся вычислении используется только конечная часть этой памяти - конечное число ячеек. В каждой ячейке ленты записан один символ из конечного внешнего алфавита машины ? = {a0, a1, … ,am }. Головка машины представляет конечный автомат, который в каждый момент времени находится в одном из внутренних состояний Q ={q0,q1,… , qn }. На каждом шаге головка в зависимости от своего внутреннего состояния и символа в ячейке, которую она наблюдает, изменяет свое внутреннее состояние и содержимое наблюдаемой ячейки и может сдвинуться на одну ячейку вправо или влево либо остаться на месте.
Дадим более формальное определение.
Определение 9.1. Машина Тьюринга - это система вида

включающая следующие компоненты:
- Q ={q0,q1,… ,qn } - внутренний алфавит (алфавит состояний);
- ? = {a0, a1, … , a{m-1} } - внешний алфавит (алфавит ленты);
-
P - программа машины, в которой для каждой пары qi
Q \ { qf }, aj? имеется (одна!) команда видаC
{Л, П, Н} задает сдвиг головки вправо, влево или на месте; - q0 Q - начальное состояние;
- qf Q - заключительное состояние.
Выделим в алфавите ? специальный пустой символ a0 =

Будем говорить, что некоторый символ стирается, если он заменяется на пустой. Два слова из ?* будем считать равными, если они совпадают после отбрасывания всех пустых символов слева и справа. Например,









Как и для конечных автоматов, программу P можно задавать с помощью таблицы размера n ? m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита ?, в которой на пересечении строки qi и столбца aj стоит тройка qk al C - правая часть команды qi aj

Определение 9.2. Назовем конфигурацией м.Т.



Будем считать, что слово wл aj wп содержит все значащие символы на ленте. Поэтому, с точностью до описанного выше равенства слов, конфигурация определена однозначно. В частности, если wл=?, т.е. пусто, то левее положения головки все ячейки пусты, а если wп=?, то правее положения головки все ячейки пусты.
Начальная конфигурация - это конфигурация вида q0w, т.е. в начальный момент времени головка в состоянии q0 обозревает первый символ входного слова w. { it Заключительная } конфигурация - это конфигурация вида w1 qf w2, в которой машина находится в заключительном состоянии qf .
Определение 9.3. Скажем, что конфигурация K= w1 qi aj w2 м.Т.



- если С=Н, то w1'=w1, w2'=w2 и a{j'}=al;
- если С=Л, то w1=w1' a, a{j'}=a, w2'=al w2 (если w1=?, / то w1' = ? и a{j'}=);
- если С=П, то w2=aw2', a{j'}=a, w1'=w1 al (если w2=?, / то w2' = ? и a{j'}=).
Как обычно, через



