Машина Тьюринга как универсальный распознаватель

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

Определение. Рекурсивно перечислимый язык — это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция), которая остановится и примет любую входную строку из этого языка.

Все регулярные, контекстно-свободные, контекстно-зависимые и рекурсивные языки являются рекурсивно перечислимыми.

Если к модели КА добавить неограниченную внешнюю память, то получим автомат, реализующий любой алгоритм. Такой автомат называется Машиной Тьюринга (МТ).

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

МТ может выполнять следующие команды:

1) записывать в ячейку ленты новый символ;

2) сдвигаться на одну ячейку влево или вправо;

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

Больше МТ ничего не может.

МТ задается: T = (Q, S, Γ, δ, q₀, F),

1) набором внутренних состояний Q={q₁…q_m};

2) начальным состоянием q₀

3) множеством заключительных состояний F

4) входным алфавитом S={S₁…S_n);

5) алфавитом допустимых символов на ленте Г

6) командами движения головки {L,R,N}.

7) программой управления δ, которую можно задавать как в текстовой, так и в табличной форме:

δ(q_i, Г_i) = (q', Г', {L,R,N})

или

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

Пример. Задать язык L = {0ⁿ1ⁿ | n ≥ 1}.

Положим МT = (Q, S, Γ, δ, q₀, F),

где Q = {q0, q1, q2, q3, q4, q5};

S = {0,1};

Γ = {0, 1, B, X, Y};

q0 = q0;

F = {q5}.

Головка находится на первом символе цепочки.

Программу МТ δ определим следующим образом:

1. δ(q0, 0) = (q1, X, R).

В состоянии q0 символ 0 заменяется на X и машина сдвигается вправо в состояние q1 в поисках 1.

2. а) δ(q1, 0) = (q1, 0, R);

б) δ(q1, Y) = (q1, Y, R);

в) δ(q1, 1) = (q2, Y, L).

Оставаясь в состоянии q1, машина продвигается вправо сквозь все нули (п. 2а) и блок Y (п. 2б). Наткнувшись на 1, заменяет ее на Y и переходит в состояние q2, начав движение влево (п. 2в).

3. а) δ(q2, Y) = (q2, Y, L);

б) δ(q2, X) = (q3, X, R);

в) δ(q2, 0) = (q4, 0, L).

Оставаясь в состоянии q2, машина продвигается влево сквозь блок Y (п. 3а). Если машина встречает X, все еще оставаясь в состоянии q2, то больше нет нулей, которые следовало бы заменять на X, и машина переходит в состояние q3, начиная движение вправо, чтобы убедиться, что не осталось единиц (п. 3б). Если же 0 встретился, машина переходит в состояние q4, чтобы продолжить движение в поисках крайнего левого 0 (п. 3в).

4. а) δ(q4, 0) = (q4, 0, L)

б) δ(q4, X) = (q0, X, R).

Машина движется сквозь нули (п. 4а). Если встретился X, то машина прошла самый левый нуль. Она должна, сдвинувшись вправо, превратить этот 0 в X (п. 4б). Происходит переход в состояние q0, и процесс, только что описанный в п. 1–4, продолжается.

5. а) δ(q3, Y) = (q3, Y, R)

б) δ(q3, B) = (q5, Y, R).

Машина входит в состояние q3, когда ни одного 0 не остается (см. п. 3б). Машина должна продвигаться вправо (п. 5а) сквозь блок Y. Если встречается пробел раньше, чем 1, то ни одной 1 не осталось (п. 5б). В этой ситуации машина переходит в конечное состояние q5 и останавливается, сигнализируя тем самым прием входной цепочки.

6. Во всех случаях, кроме 1–5, функция δ не определена. МТ остановится и отвергнет входную цепочку.

Табличная запись функции δ.

			X	Y	В
q0	q1, X, R	отв.	отв.	отв.	отв.
q1	q1, 0, R	q2, Y, L	отв.	q1, Y, R	отв.
q2	q4, 0, L	отв.	q3, X, R	q2, Y, L	отв.
q3	отв.	отв.	отв.	q3, Y, R	q5, Y, R
q4	q4, 0, L	отв.	q0, X, R	отв.	отв.

Рассмотрим действия машины Тьюринга на входной цепочке 000111.

В таблице приведены конфигурации в виде цепочек символов ленты с маркером состояния под сканируемым символом (в конфигурациях 25 и 26 маркер состояния находится под символом пробела).

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

Пример. Задать язык, состоящий из цепочек, в которых первый символ повторно не встречается в той же самой цепочке.

Пусть МT = (Q, {0, 1},{0, 1, B}, δ, [q0, B], F),

где Q = {[q0, 0],[q0, 1], [q0, B], [q1, 0], [q1, 1], [q1, B]},

F = {[q1, B]}, т.е. здесь Q записано как {q0, q1} × {0, 1, B}.

Построим функцию δ (программу МТ) следующим образом:

1. а) δ([q0, B], 0) = ([q1, 0], 0, R);

б) δ([q0, B], 1) = ([q1, 1], 1, R).

Машина запоминает сканируемый символ во второй компоненте обозначения состояния и сдвигается вправо. Первой компонентой становится q1.

2. а) δ([q1, 0], 1) = ([q1, 0], 1, R);

б) δ([q1, 1], 0) = ([q1, 1], 0, R).

Если машина помнит 0 и видит 1 или, наоборот, помнит 1 и видит 0, то она продолжает движение вправо.

3. а) δ([q1, 0], B) = ([q1, B], 0, L);

б) δ([q1, 1], B) = ([q1, B], 0, L).

Машина входит в конечное состояние [q1, B], если она встречает символ пробела раньше, чем достигает второй копии самого левого символа. Если же машина достигает пробела в состоянии [q1, 0] или [q1, 1], то она принимает входную цепочку. Для состояния [q1, 0] и символа 0 или для состояния [q1, 1] и символа 1 функция δ не определена, так что, если машина когда-нибудь видит запомненный символ, она останавливается, не принимая.

Табличная запись функции δ.