ГЛАВА 2. Неразрешимые языки и проблемы

Вопросы неразрешимости языков и проблем, решаемые с помощью машин Тьюринга, не подвержены тем ограничениям, которые возникают при реализации языка на реальном компьютере, связанные с конечным объемом адресного пространства, оперативной памяти и т.п. Далее будут предложены некоторые (неразрешимые) языки, используемые в дальней шем для доказательства неразрешимости других языков (проблем).

(A) Допускает ли машина Тьюринга сама себя (свой код) в качестве

входа ?

(B) Допускает ли данная машина данный вход ?

В дальнейшим мы обнаружим, что все нетривиальные задачи, связанные с языком машины Тьюринга, неразрешимы.

Как уже было сказано, допустимые машинами Тьюринга языки называются рекурсивно перечислимыми. Допускающие язык L машины M останавливаются на словах (цепочках) wÎL=L(M), а на словах wÏL могут также останавливаться, не допуская, такие языки L будем называть рекурсивными (разрешимыми), или - работать бесконечно, назовем такие языки нерекурсивными (неразрешимыми). К неразрешимым языкам отнесем и не рекурсивно перечислимые (неперечислимые) языки, существование которых нам предстоит доказать.

Неперечислимый язык.

Перечислим машины Тьюринга и входы, перечисляя их коды в алфавите {0,1}. Пустой цепочке припишем номер 1, цепочке “0” - номер 2, цепочке “1” – номер 3, цепочке “00” – номер 4, цепочке “01” – номер 5, остальное перечисление цепочек становится очевидным. В дальнейшем цепочку с номером i будем обозначать через w_i .

Представим код машины Тьюринга M как двоичную цепочку. Состояние q_i и ленточный символ X_i кодируются в виде i нулей, отделяемых 1, пустой символ кодируется цепочкой w₁. Направления R,L,S представим как некоторые цепочки D_m из 0. Переход q_i X_j ® X_l R q _k закодируется естественным образом цепочкой 0ⁱ10^j10^l10^m10^k (где i,j,l,m,k ³1). Если C₁,…,C_к - коды всех переходов машины Тьюринга, то C₁11С₂11…11C_к - код самой машины M.

Коды машин Тьюринга представлены двоичными цепочками, которые в свою очередь являются представлениями натуральных чисел в двоичной системе. Такое натуральное число будем считать номером машины в перечисление машин Тьюринга. Иначе машина M_i , или i-ая машина, Тьюринга имеет своим кодом цепочку w_i , и номер i. Очевидно, что не все двоичные цепочки w_i являются правильными кодами машин Тьюринга, в этом случае будем считать, что машина M_i имеет одно состояние и у нее нет переходов, т.е. такая машина M_i останавливается сразу на любом входе. Также для нее L(M_i) = Æ.

Теперь можно представить таблицу, у которой по горизонтали стоят номера всех цепочек, а по вертикали номера всех машин Тьюринга

(все натуральные числа), а на пересечении i-й строки и j-го столбца стоит 1, если машина M_i допускает цепочку w_j , и 0 – если не допускает.

Числа по главной диагонали показывают, допускает ли машина M_i цепочку w_i. Построим язык L_d такой, что w_i Î L_d « w_i Ï M_i .

L_d называют языком диагонализации. Очевидно, что он не попадает в перечисление языков машин Тьюринга, т.е. нет допускающей его машины Тьюринга.

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

Доказательство. Допустим противное, что существует машина M_i , допускающая язык L_d , так что L_d = L(M_i). Теперь, если M_i допускает w_i ,

то w_i ÎL(M_i) = L_d , однако согласно определению языка L_d , w_i Ï L_d ; если M_i не допускает w_i , т.е. w_i Ï L(M_i) = L_d, но по определению языка L_d, w_i Î L_d . Откуда w_i Î L_d « w_i Ï L_d , что образует противоречие. Таким образом, не существует машины, допускающей язык L_d , а следовательно, язык диагонализации L_d не является рекурсивно перечислимым языком. “

Рекурсивные языки. Неразрешимая РП – проблема.

Язык L называется рекурсивным, если он допускается некоторой машиной Тьюринга M, т.е. L=L(M) и :

1) если wÎL, то M допускает вход w, следовательно, останавливается;

2) если wÏL, то M в конце концов остановится, не допуская.

Если мы рассматриваем язык L как проблему, то проблема называется разрешимой, если язык L рекурсивный. В противном случае проблема называется неразрешимой.

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

1. Рекурсивные языки.

2. Рекурсивно перечислимые (РП), не являющиеся рекурсивными.

3. Неперечислимые (не - РП) языки.

Рис 9.2

Теорема.Если L - рекурсивный язык, то язык L , дополнение языка L , также рекурсивный.

Доказательство. Пусть L=L(M), где машина M останавливается на всех входах. Построим машину Тьюринга M , у которой L = L(M). Для чего надо переделать заключительные состояния машины M в недопускающие, не имеющие переходов, и добавив новое допускающее состояние r, передать управление из каждого недопускающего состояния в r. “

Теорема (Поста).Если язык L и его дополнение рекурсивно перечислимы, то L рекурсивен.

Доказательство. Пусть L=L(M₁) и L =L(M₂). Возьмем машину Тьюринга M с двумя лентами, имитирующими соответственно машины M₁ и M₂.

Пусть вход w Î L, тогда M₁ допускает w, а машина M допускает и останавливается; в противном случае машина M останавливается, не допуская. Таким образом, машина M останавливается на любом входе и L= L(M), т.е. L рекурсивный язык. “

Следствие. Из девяти способов соотношений языков L и L^’ возможны следующие четыре:

1. Оба языка L и L^’ рекурсивны.

2. Ни L, ни L^’ не являются рекурсивно перечислимыми.

3. L является рекурсивно перечислимым, а L^’ не рекурсивно перечислим.

4. L^’ является рекурсивно перечислимым, а L не рекурсивно перечислим.

Универсальный язык L_u определяется как множество цепочек в алфавите {0,1}, являющихся кодами упорядоченных пар (M, w), где M - машина Тьюринга с входным алфавитом {0,1} и w - цепочка из {0,1}*, принадлежащая L(M). Код упорядоченной пары (M,w) представляется кодом машины M, отделенным 111 от кода цепочки w. Другими словами, язык L_u - это множество цепочек, кодов упорядоченных пар (M,w), представляющих машину Тьюринга и допускаемый ею вход. Покажем, что существует машина Тьюринга U, называемая универсальной машиной, для которой L_u = L(U).

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

Пусть на 1-й ленте машины U хранятся переходы машины M вместе с входом w; на 2-й ленте – двоичный код машины M; на 3-й - состояние машины M; 4-ая - рабочая лента. Схема U представлена на рис.

Рис стр 387

Машина U производит следующие операции:

1. Исследует вход, и если код M правильный, записывает на 2-ю ленту код входной цепочки w. Для неправильных кодов M машина U не допускает никакого входа.

2. На 2-й ленте все клетки, кроме занятых кодом входа w, заполняются символом L, представляемым как 1000.

3. На 3-й ленте записывается 0, т.е. начальное состояние q₀ машины M, и считывающая головка обозревает первый символ кода w.

4. Чтобы отобразить переход машины M, машина U отыскивает его на первой ленте, например, 0ⁱ 10^j 10^k 10^l 10^m (m=1,2,3 – кодирует R,L,S),

и выполняет следующие действия:

a) изменяет содержимое 3-ей ленты на 0^k;

b) заменяет 0^j на второй ленте на 0^l ;

c) перемещает головку на 2-й ленте согласно 0^m .

5. Если M не имеет перехода, то M останавливается, и U останавливается.

6. Если M попадает в допускающее состояние, то U допускает.

Таким образом, U допускает вход (M,w) тогда и только тогда, когда M допускает w. “