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

Обучение онлайн!

 

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

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

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

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

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

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

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

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

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

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

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

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

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

[collapse]
Такт работы машины Тьюринга

Такт работы машины Тьюринга


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

1) записывает некоторый символ S′ в видимую клетку (в частности, может быть записан тот же символ, что и был в ней, тогда содержимое этой клетки не меняется);
2) сдвигается на одну клетку влево (обозначение – L, от left), либо на одну клетку вправо (обозначение – R, от right), либо остается неподвижным (обозначение – N).
3) переходит в некоторое состояние q′ (в частности, может остаться в прежнем состоянии).

Формально действия одного такта будем записывать в виде тройки: S′, [L,R,N], q′
где конструкция с квадратными скобками означает возможность записи в этом месте любой из букв L, R или N. Например, такт *,L,q8 означает запись символа * в видимую клетку, сдвиг на одну клетку влево и переход в состояние q8.

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

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


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

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

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

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

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


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

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

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


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


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

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

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

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

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


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


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

 

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


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

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

a,R,q3 ≡ ,R,q3 (но не λ,R,q3!!)
b,N,q2 ≡ b, ,q2
a,L,q1 ≡ ,L,
a,N,q1 ≡ , , (это такт останова)

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

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

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

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

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

[collapse]

Примеры составления программ для МТ

1. Перемещение автомата, замена символа.

Задан алфавит входного слова А={0,1,2,3,4,5,6,7,8,9}. Пусть Р – входное непустое слово, то есть Р – последовательность из десятичных цифр, т.е. запись неотрицательного числа в десятичной системе. Требуется получить на запись числа,