Машина Тьюринга как универсальный распознаватель
Как известно, с помощью МТ можно задать очень широкий класс языков, называемый рекурсивно перечислимым.
Определение.Рекурсивно перечислимый язык — это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция), которая остановится и примет любую входную строку из этого языка.
Все регулярные, контекстно-свободные, контекстно-зависимые и рекурсивные языки являются рекурсивно перечислимыми.
Если к модели КА добавить неограниченную внешнюю память, то получим автомат, реализующий любой алгоритм. Такой автомат называется Машиной Тьюринга (МТ).
МТ состоит из 2 частей: ленты и конечного автомата. Обычно в моделях МТ лента неподвижна, а головка движется относительно ленты под управлением автомата (влево, вправо, стоит на месте).
МТ может выполнять следующие команды:
1) записывать в ячейку ленты новый символ;
2) сдвигаться на одну ячейку влево или вправо;
3) переходить в новое внутреннее состояние.
Больше МТ ничего не может.
МТ задается: T = (Q, S, Γ, δ, q0, F),
1) набором внутренних состояний Q={q1…qm};
2) начальным состоянием q0
3) множеством заключительных состояний F
4) входным алфавитом S={S1…Sn);
5) алфавитом допустимых символов на ленте Г
6) командами движения головки {L,R,N}.
7) программой управления δ, которую можно задавать как в текстовой, так и в табличной форме:
δ(qi, Гi) = (q', Г', {L,R,N})
или
Будем предполагать, что МТ, распознающая язык L, останавливается, т.е. не имеет никакого следующего движения, всякий раз, как входная цепочка принимается.
Пример. Задать язык L = {0n1n | n ≥ 1}.
Положим МT = (Q, S, Γ, δ, q0, 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 функция δ не определена, так что, если машина когда-нибудь видит запомненный символ, она останавливается, не принимая.
Табличная запись функции δ.
| В | |||
| [q0,B] | [q1, 0], 0, R | [q1, 1], 1, R | [q0,B], В, R |
| [q1,0] | отв. | [q1, 0], 1, R | допущена |
| [q1,1] | [q1, 1], 0, R | отв. | допущена |
В общем случае можно допустить произвольное фиксированное число компонент, причем все, кроме одной, предназначены для запоминания информации.