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

Рассматриваемая в этом разделе модель алгоритмов была предложена английским математиком Тьюрингом в 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 =

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

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

c = ab

c, но ab

abc.

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

qk al C.

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

в некоторый момент времени слово K= wл qi aj wп, где wл

?* - слово на ленте левее текушего положения головки, qi - внутреннее состояние в данный момент, aj- символ, обозреваемый головкой, wп

?* - слово на ленте правее текушего положения головки.

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

Начальная конфигурация - это конфигурация вида q0w, т.е. в начальный момент времени головка в состоянии q0 обозревает первый символ входного слова w. { it Заключительная } конфигурация - это конфигурация вида w1 qf w2, в которой машина находится в заключительном состоянии qf .

Определение 9.3. Скажем, что конфигурация K= w1 qi aj w2 м.Т.

за один шаг (такт) переходит в конфигурацию

если в программе имеется команда qi aj

qk al C и при этом,

если С=Н, то 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'}=
).

Как обычно, через

обозначим рефлексивное и транзитивное замыкание отношения

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

будем опускать).

Содержание раздела