Основные определения

Рассматриваемая в этом разделе модель алгоритмов была предложена английским математиком Тьюрингом в 1937 г. еще до создания современных компьютеров¹⁾ Он исходил из общей идеи моделирования работы вычислителя, оперирующего в соответствии с некоторым строгим предписанием. В машине Тьюринга расчленение процессавычисления на элементарные шаги доведено в известном смысле до предела. Элементарным действием является замена одного символа в ячейке на другой и перемещение к соседней ячейке. При таком подходе процесс вычисления значительно удлиняется, но зато логическая структура процесса сильно упрощается и приобретает удобный для теоретического исследования вид.

Машина Тьюринга (м.Т.) состоит из неограниченной в обе стороны ленты, разбитой на ячейки, по которой передвигаетсяголовка машины. Такая "бесконечность" ленты является математической абстракцией, отражающей потенциальную неограниченность памяти вычислителя. Разумеется, в каждом завершающемсявычислении используется только конечная часть этой памяти - конечное число ячеек. В каждой ячейке ленты записан один символ из конечного внешнего алфавита машины . Головка машины представляет конечный автомат, который в каждый момент времени находится в одном из внутренних состояний Q ={q₀,q₁,... , q_n }. На каждом шаге головка в зависимости от своего внутреннего состояния и символа в ячейке, которую она наблюдает, изменяет свое внутреннее состояние и содержимое наблюдаемой ячейки и может сдвинуться на одну ячейку вправо или влево либо остаться на месте.

Дадим более формальное определение.

Определение 9.1. Машина Тьюринга - это система вида

включающая следующие компоненты:

• Q ={q₀,q₁,... ,q_n } - внутренний алфавит (алфавит состояний);
• - внешний алфавит (алфавит ленты );

· P - программа машины, в которой для каждой пары имеется (одна!)команда вида

задает сдвиг головки вправо, влево или на месте;

• - начальное состояние;
• - заключительное состояние.

Выделим в алфавите специальный пустой символ и будем считать, что во всех ячейкахленты, кроме конечного их числа, в начальный и во все последующие моменты находится пустой символ.

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

Как и для конечных автоматов, программу P можно задавать с помощью таблицы размера n x m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита в которой на пересечении строки q_i и столбца a_j стоит тройка q_k a_l C - правая часть команды q_i a_j -> q_k a_l C.

Определение 9.2. Назовем конфигурацией м.Т. в некоторый момент времени слово K= w_л q_i a_jw_п, где - слово на ленте левее текушего положения головки, q_i - внутреннее состояние в данный момент, a_j - символ, обозреваемый головкой, - слово на ленте правее текушего положения головки.

Будем считать, что слово w_л a_j w_п содержит все значащие символы на ленте. Поэтому, с точностью до описанного выше равенства слов, конфигурация определена однозначно. В частности, если , т.е. пусто, то левее положения головки все ячейки пусты, а если , то правее положенияголовки все ячейки пусты.

Начальная конфигурация - это конфигурация вида q₀w, т.е. в начальный момент времени головка в состоянии q₀ обозревает первый символ входного слова w. { it Заключительная } конфигурация - этоконфигурация вида w₁ q_f w₂, в которой машина находится в заключительном состоянии q_f.

Определение 9.3. Скажем, что конфигурация K= w₁ q_i a_j w₂ м.Т. за один шаг (такт) переходит вконфигурацию , если в программе имеется команда q_i a_j -> q_k a_l Cи при этом,

• если С=Н, то w₁^'=w₁, w₂^'=w₂ и a_{j^'}=a_l;
• если С=Л, то w₁=w₁^' a, a_{j^'}=a, w₂^'=a_l w₂ (если то и );
• если С=П, то w₂=aw₂^', a_{j^'}=a, w₁^'=w₁ a_l (если то и ).

Как обычно, через обозначим рефлексивное и транзитивное замыкание отношения а будет означать, что конфигурация K за n шагов переходит в K^'. (Если из контекста ясно, о какой машине идет речь, то индекс будем опускать).

Пример 9.1.

Рис. 9.1. Выполнение команды q3 0 -> q5 1 П

Например, ситуации, представленной на рис.9.1 слева соответствует конфигурация . Предположим, что программа P содержит команду q₃0 -> q₅1 П. Тогда после выполнения этойкоманды K перейдет за один шаг в конфигурацию , показанную на этом рисунке справа. Следовательно, .

Определение 9.4. Вычисление м.Т. на входе w - это конечная или бесконечная последовательность конфигураций такая, что K₀=q₀w - начальнаяконфигурация. Эта последовательность конечна, когда ее последняя конфигурация K_n= v₁ q_f v₂ - заключительная. В этом случае вычисление назовем результативным, а слово v = v₁ v₂ - его результатом на входе w (всегда будем предполагать, что v не содержит пустых символов слева и справа).

Определение 9.5. Скажем, что м.Т. вычисляет частичную словарную функцию если для каждого слова w из области определения f существует результативное вычисление