Неразрешимость. 
Сложность вычислений

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

§ 2. Коды машины Тьюринга.

§ 3. Язык диагонализации L_d

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

§ 5. Универсальный язык L_u

§ 6. Языки L_e и L_ne

§ 7. Проблема соответствий Поста.

Самостоятельные занятия:

[1], глава 9.

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

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

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

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

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

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

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

Представим код машины Тьюринга M как двоичную цепочку. Состояние qi и ленточный символ Xi кодируются в виде i нулей, отделяемых 1, пустой символ кодируется цепочкой 1. Направления R, L, S представим как некоторые цепочки Dm из 0. Переход qi Xj Xl R q k закодируется естественным образом цепочкой 0ⁱ10^j10^l10^m10^k (где i, j, l, m, k 1). Если C1,…,Cк — коды всех переходов машины Тьюринга, то C111С211…11Cк — код самой машины M.

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

Теперь можно представить таблицу, у которой по горизонтали стоят номера всех цепочек, а по вертикали номера всех машин Тьюринга (все натуральные числа), а на пересечении i-й строки и j-го столбца стоит 1, если машина M_i допускает цепочку _j, и 0 — если не допускает.

Числа по главной диагонали показывают, допускает ли машина M_i цепочку _i. Построим язык L_d такой, что _i L_{d i} M_i .

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

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

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

то _i L (M_i) = L_d, однако согласно определению языка L_d, _i L_d; если M_i не допускает _i, т. е. _i L (M_i) = L_d, но по определению языка L_d, _i L_d. Откуда _i L_{d i} L_d, что образует противоречие. Таким образом, не существует машины, допускающей язык L_d, а следовательно, язык диагонализации L_d не является рекурсивно перечислимым языком.

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

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

• 1) если L, то M допускает вход, следовательно, останавливается;
• 2) если L, то M в конце концов остановится, не допуская.

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

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

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

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

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

Теорема. Если 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₂.

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

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

• 1. Оба языка L и L' рекурсивны.
• 2. Ни L, ни L' не являются рекурсивно перечислимыми.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Неразрешимость универсального языка. Проблема останова Существуют рекурсивно перечислимые, но не рекурсивные языки, один из таких языков L_u. Сведением L_u к проблеме P можно доказать, что P не имеет алгоритма.

Теорема. Язык L_u рекурсивно перечислим, но не рекурсивен.

Доказательство. Была доказана рекурсивная перечислимость языка L_u. Допустим, что L_u рекурсивен, тогда по теореме язык L_u рекурсивен и существует допускающая его машина M, т. е. L_u = L (M). Преобразуем M в машину M ', допускающую L_u: если вход есть _i, т. е. код машины M_i, то M ' определяет, допускает ли M_i вход _i. Поскольку M допускает L_u, то M допускает _i, если M_i не допускает _i, т. е. когда _i L_d.

Таким образом, M ' допускает тогда и только тогда, когда L_d.

Поскольку по теореме машины M ' не существует, получено противоречие, следовательно, язык L_u не является рекурсивным.

Неразрешимые проблемы, связанные с машинами Тьюринга В математической логике рассматриваются разные типы сведений, образующие целую ветвь математической логики, теорию степеней неразрешимости. В общем виде, проблема P₁ сводима к проблеме P₂ (P₁ < _f P₂), если существует вычислимая функция f такая, что.

xP₁ f (x)P₂ (xP₁ f (x)P₂).

В этом случае говорят, что проблема P₂ не менее трудна, чем проблема P₁.

Теорема. Если P₁ < _f P₂, то.

если P₁ не является рекурсивной, то P₂ также не рекурсивна (не-Р);

если P₁ не является рекурсивно перечислимой, то P₂ не рекурсивно перечислима (не-РП).

Доказательство. a) Допустим, что P₁ не рекурсивно, а P₂ рекурсивно.

На входе P₁, так как P₁ < _f P₂, то f ()P₂. Так как P₂ рекурсивно, существует алгоритм A:

A (x)=0, если x P₂, где x = f (), тогда и только тогда, когда P₁;

A (x)=1, если x P₂, где x = f (), тогда и только тогда, когда P₁.

Откуда следует, что P₁ рекурсивно, по противоречию P₂ — не рекурсивно.

Пусть P₁ не-РП, а P₂ — рекурсивно перечислимо. Тогда P₂ имеет допускающую ее машину M₂. Если на входе x P₂ машина M₂ допускает, тогда P₁, где x=f (); в противном случае машина M₂ работает бесконечно, следовательно, и P₁. Таким образом, машина, языком котором является P₁, допускает или не допускает свой вход одновременно с машиной M₂, и, следовательно, допускает язык P₁, что противоречит условию.

Наряду с введенными выше языками L_d и L_u в теории сложности представляют интерес взаимо дополняющие друг друга в {0,1}* языки:

L_e = {M: L (M) = } (кодов мащин, допускающих пустой язык) и.

L_ne = {M: L (M) }, над алфавитом {0,1}, представленные кодами машин Тьюринга.

Теорема. Язык L_ne рекурсивно перечислим.

Доказательство. Для доказательства достаточно построить допускающую язык L_ne машину Тьюринга. Пусть это недетерминированная машина M, изображенная на рис.

Рис. 9.8. Конструкция НМТ, допускающей язык L_ne

Работа машины M состоит в следующем:

• 1) получив на вход код машины M_i, используя способность недетерминированной машины угадывать вход, на котором машина M_i, воможно, допускает,
• 2) машина M проверяет, допускает ли машина M_i на входе, моделируя работу машины U;

если (M_i,) L_u, т. е. машина M_i допускает на входе, то машина.

M также допускает на своем входе M_i, в противном случае работает бесконечно.

Таким образом, L (M) = L_ne .

Теорема. Язык L_ne не является рекурсивным.

Доказательство. Построим функцию (алгоритм), сводящий универсальный язык L_u к языку L_ne, т. е. вход (M,) машины U преобразуем во вход машины M ', допускающей язык L_ne. Машина M ' моделирует машину M на входе и если (M,) L_u, то (M ', x) L_u, где x произвольный вход машины M '. В этом случае машина M' допускает хотя бы одну цепочку, т. е. L (M') и M ' L_ne. Аналогично, в случае, если (M,) L_u, L (M ') = и M' L_ne. Схема машины M ', построенной по (M,) приведена на рис.

Машина M ' по построению выполняет следующие действия:

Машина M ' строится по конкретной паре (M,), имеюшей длину n, тогда q₀ ,…, q_n состояния M ' (где q₀ — начальное состояние).

a) В состоянии q_i (i=0,., n-1) машина M ' записывает (i+1)-й бит кода (M,) и переходит в состояние q_i+1, сдвигаясь вправо.

b) В состоянии q _n, в случае необходимости, M ' сдвигается вправо и заполняет все непустые клетки (хвост x, если длина цепочки x больше n) пробелами.

Когда M ' достигает пробела с состоянии q_n, она, используя похожий набор состояний, перемещает головку в левый конец ленты.

Используя дополнительные состояния M ' моделирует универсальную машину U.

Если U допускает, то M ' допускает. Если U никогда не допускает, то M ' никогда не допускает.

Из схемы работы машины видно, что если M допускает вход, то M ' допускает свой вход x, который первоначально был записан на ленте, следовательно, M ' L_ne. В противном случае, если M не допускает вход, то M ' не допускает любой свой вход x, записанный на ленте, тогда M ' L_ne. Таким образом, L_u сводимо к L_ne с помощью алгоритма, который строит M' по данным M и. Поскольку, L_u не является рекурсивным, то L_ne также не рекурсивен.

Теперь известен и статус языка L_e. Если бы L_e был бы рекурсивно перечислимым, то по теореме и он, и его дополнение L_ne были бы рекурсивными. Однако было доказано, что язык L_ne не рекурсивен.

Теорема. Язык L_e не является рекусивно перечислимым.

Теорема Райса и свойства РП-языков Неразрешимость языков L_e и L_ne есть только частный случай более общей теоремы о неразрешимости любого нетривиального свойства РП-языков.

Свойством РП-языков называют множество РП-языков. Например, свойства «быть контексно-свободным языком» или «быть регулярным языком» представлены соответственно множествами контекстно-свободных и регулярных языков. Тривиальным свойством называют множество из одного пустого языка или из всех РП-языков. В противном случае свойство называют нетривиальным.

Пусть — свойство РП-языков, а L — множество кодов машин M_i таких, что L (M_i) .

Теорема (Райса). Всякое нетривиальное свойство РП-языков неразрешимо.

Доказательство. Пусть — свойство РП-языков и () ().

a) Допустим, что, тогда существует непустой язык L, пусть xL. Построим алгоритм, сводящий L_u к L. По паре (M,) строится машина M ' такая, что (M,) L_u M ' L:

Если (M,) L_u, т. е. M не допускает вход, тогда M ' прекращает работу, не допуская свой вход x. L (M') =, следовательно,.

L (M '), а M' L. Если (M,) L_u, то L (M') = L и M' L.

Схема такого алгоритма приведена на рис.

Машина M' имеет две ленты: на первой записан код машины M и входа, на второй — код машины M_L, допускающей язык L.

Работа моделируемой машины M' состоит в следующих шагах:

Имитируется работа универсальной машины U на входе (M,).

Если (M,) L _u, т. е. M не допускает вход, то M' прекращает работу, не допуская свой вход x.

Если (M,) L _u, т. е. M допускает, то далее M' имитирует работу машины M_L на входе x и допускает, так как xL и M_L допускает язык L.

Таким образом, для рассматриваемого свойства, где, L_u < L _, следовательно, язык L неразрешим.

b) Допустим, что. Рассмотрим, дополнение свойства, т. е. множество РП-языков, не обладающих свойством. Свойство содержит, так что как в части a) можно доказать неразрешимость языка L. Поскольку язык L есть множество кодом машин, не допускающих свойство, то L = L. Если предположить, что язык L разрешимый, то по теореме Поста, его дополнение — рекурсивный язык, что не верно.

Неразрешимые проблемы, связанные с языками машин Тьюринга:

Пуст ли язык, допускаемый машиной Тьюринга?

Конечен ли язык, допускаемый машиной Тьюринга?

Регулярен ли язык, допускаемый машиной Тьюринга?

Контекстно-свободен язык, допускаемый машиной Тьюринга?

Разрешимые (тривиальные) проблемы, связанные с языками машины Тьюринга:

Содержит ли машина Тьюринга данное число состояний?

Существует ли вход, допускаемый машиной Тьюринга за данное число переходов?