Дискретная математика. Машина Тьюринга.

Структура машины Тьюринга (МТ)

Машина Тьюринга (МТ) состоит из двух частей – ленты и автомата

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

Содержимое клетки может меняться – в неё можно записать другой символ или стереть находящийся там символ. Договоримся пустое содержимое клетки называть символом «пусто» и обозначать знаком λ («лямбда»).

Автомат – это активная часть МТ. В каждый момент он размещается под одной из клеток ленты и видит её содержимое; это ВИДИМАЯ клетка, а находящийся в ней символ – ВИДИМЫЙ символ; содержимое соседних и других клеток автомат не видит.

Кроме того, в каждый момент автомат находится в одном из состояний, которые будем обозначать буквой q с номерами: q₁, q₂ и т.п. Находясь в некотором состоянии, автомат выполняет какую-то определённую операцию (например, перемещается направо по ленте, заменяя все символы b на a), находясь в другом состоянии – другую операцию.

Пару из видимого символа (S) и текущего состояния автомата (q) будем называть конфигурацией и обозначать <S, q>.

Автомат может выполнять три элементарных действия:

1) записывать в видимую клетку новый символ (менять содержимое других клеток автомат не может);

2) сдвигаться на одну клетку влево или вправо («перепрыгивать» сразу через несколько клеток автомат не может);

3) переходить в новое состояние.

Ничего другого делать автомат не умеет, поэтому все более сложные операции так или иначе должны быть сведены к этим трём элементарным действиям.

Программа для машины Тьюринга

Сама по себе МТ ничего не делает. Для того чтобы заставить её работать, надо написать для неё программу. Эта программа записывается в виде следующей таблицы:

 Слева перечисляются все состояния, в которых может находиться автомат, сверху – все символы (в том числе и λ), которые есть на ленте. (Какие именно символы и состояния указывать в таблице – определяет автор программы). На пересечениях же (в ячейках таблицы) указываются те такты, которые должен выполнить автомат, когда он находится в соответствующем состоянии и видит на ленте соответствующий символ.

Таблица полностью задаёт поведение МТ. Описать алгоритм в виде МТ – значит предъявить такую таблицу.

Замечание. Часто МТ определяют как состоящую из ленты, автомата и программы, поэтому при разных программах получаются разные МТ. Мы же
будет считать, в духе современных компьютеров, что МТ одна, но она может выполнять разные программы.

Правила выполнения программы

До выполнения программы нужно проделать следующие предварительные действия.

• во-первых, надо записать на ленту входное слово, к которому будет применена программа. Входное слово – это конечная последовательность символов, записанных в соседних клетках ленты; внутри входного слова пустых клеток быть не должно, а слева и справа от него должны быть только пустые клетки. Пустое входное слово означает, что все клетки ленты пусты.
• во-вторых, надо установить автомат в состояние q₁ (указанное в таблице первым) и разместить его под первым символом входного слова;
• если входное слово пустое, то автомат может смотреть в любую клетку, т.к. все они пусты.

После этих предварительных действий начинается выполнение программы. В таблице отыскивается ячейка на пересечении первой строки (т.к. автомат находится в состоянии q₁) и того столбца, который соответствует первому символу входного слова (это необязательно левый столбец таблицы), и выполняется такт, указанный в этой ячейке. В результате автомат окажется в новой конфигурации. Теперь такие же действия повторяются, но уже для новой конфигурации: в таблице отыскивается ячейка, соответствующая состоянию и символу этой конфигурации, и выполняется такт из этой ячейки. И так далее.

Когда завершается выполнение программы? Такт останова — это такт, который ничего не меняет: автомат записывает в видимую клетку тот же символ, что и был в ней раньше, не сдвигается и остается в прежнем состоянии, т.е. это такт S,N,q для конфигурации <S, q>. Попав на такт останова, МТ, по определению, останавливается, завершая свою работу.

В целом возможны два исхода работы МТ над входным словом:

1) первый исход – «хороший»: это когда в какой-то момент МТ останавливается (попадает на такт останова). В таком случае говорят, что МТ применима к заданному входному слову. А то слово, которое к этому моменту получено на ленте, считается выходным словом, т.е. результатом работы МТ, ответом.

В момент останова должны быть выполнены следующие обязательные условия:

– внутри выходного слова не должно быть пустых клеток (отметим, что во время выполнения программы внутри обрабатываемого слова пустые клетки могут быть, но в конце их уже не должно остаться);
– автомат обязан остановиться под одним из символов выходного слова (под каким именно – не играет роли), а если слово пустое – под любой клеткой ленты.

2) второй исход – «плохой»: это когда МТ зацикливается, никогда не попадая на такт останова (например, автомат на каждом шаге сдвигается вправо и потому не может остановиться, т.к. лента бесконечна). В этом случае говорят, что МТ неприменима к заданному входному слову. Ни о каком результате при таком исходе не может идти и речи.

Отметим, что один и тот же алгоритм (программа МТ) может быть применимым к одним входным словам (т.е. останавливаться) и неприменимым к другим (т.е. зацикливаться). Таким образом, применимость/неприменимость зависит не только от самого алгоритма, но и от входного слова.

На каких входных словах алгоритм должен останавливаться? На, так сказать, хороших словах, т.е. на тех, которые относятся к допустимым исходным данным решаемой задачи, для которых задача осмысленна. Но на ленте могут быть записаны любые входные слова, в том числе и те, для которых задача не имеет смысла; на таких словах поведение алгоритма не фиксируется, он может остановиться (при любом результате), а может и зациклиться.

Соглашения для сокращения записи

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

Например, при конфигурации <a, q1> следующие записи тактов эквивалентны:

a,R,q₃ ≡ ,R,q₃ (но не λ,R,q3!!)
b,N,q₂ ≡ b, ,q₂
a,L,q₁ ≡ ,L,
a,N,q₁ ≡ , , (это такт останова)

• • • • • Запятые в тактах желательно не опускать, т.к. иначе возможна путаница, если среди символов на ленте могут встретиться буквы L и R.

2. Если надо указать, что после выполнения некоторого такта МТ должна остановиться, то в третьей позиции этого такта будем писать знак «!».

Например, такт b,L,! означает следующие действия: запись символа b в видимую клетку ленты, сдвиг влево и останов. Формально можно считать, что в программе МТ имеется состояние с названием !, во всех ячейках которого записаны такты останова. При этом, однако, такую строку явно не выписывают, а лишь подразумевают.

3. Если заранее известно, что в процессе выполнения программы не может появиться некоторая конфигурация, тогда, чтобы подчеркнуть это явно, будем в соответствующей ячейке таблицы рисовать крестик. (Формально этот крестик считается тактом останова.)

Эти соглашения необязательны, но они сокращают запись программы и упрощают её восприятие. .