В математической логике рассматриваются разные типы сведений, образующие целую ветвь математической логики, теорию степеней неразрешимости. В общем виде, проблема P1 сводима к проблеме P2
(P1 < f P2 ), если существует вычислимая функция f такая, что
xÎP1 « f(x)ÎP2 (xÏP1 « f(x)ÏP2).
В этом случае говорят, что проблема P2 не менее трудна, чем проблема P1.
Теорема. Если P1 < f P2 , то
a) если P1 не является рекурсивной, то P2 также не рекурсивна (не-Р);
b) если P1 не является рекурсивно перечислимой, то P2 не рекурсивно перечислима (не-РП).
Доказательство. a) Допустим, что P1 не рекурсивно, а P2 рекурсивно.
На входе wÎP1 , так как P1 < f P2 , то f(w)ÎP2. Так как P2 рекурсивно, существует алгоритм A:
A(x)=0, если xÎ P2, где x = f(w), тогда и только тогда, когда wÎ P1;
A(x)=1, если xÏ P2, где x = f(w), тогда и только тогда, когда wÏ P1.
Откуда следует, что P1 рекурсивно, по противоречию P2 – не рекурсивно.
b) Пусть P1 не-РП, а P2 – рекурсивно перечислимо. Тогда P2 имеет до-
пускающую ее машину M2. Если на входе xÎ P2 машина M2 допускает, тогда wÎP1 , где x=f(w); в противном случае машина M2 работает бесконечно, следовательно, и wÏP1 . Таким образом, машина, языком котором является P1 , допускает или не допускает свой вход одновременно с машиной M2 , и, следовательно, допускает язык P1, что противоречит условию. “
Наряду с введенными выше языками Ld и Lu в теории сложности представляют интерес взаимо дополняющие друг друга в {0,1}* языки:
Le = {M: L(M) = Æ} (кодов мащин, допускающих пустой язык) и
Lne = {M: L(M) ¹ Æ}, над алфавитом {0,1}, представленные кодами машин Тьюринга.
Теорема. Язык Lne рекурсивно перечислим.
Доказательство. Для доказательства достаточно построить допускающую язык Lne машину Тьюринга. Пусть это недетерминированная машина M,
изображенная на рис.
Рис. 9.8. Конструкция НМТ, допускающей язык Lne
Работа машины M состоит в следующем:
1) получив на вход код машины Mi , используя способность недетерминированной машины угадывать вход w, на котором машина Mi, воможно, допускает,
2) машина M проверяет, допускает ли машина Mi на входе w, моделируя работу машины U;
3) если (Mi, w)Î Lu , т.е. машина Mi допускает на входе w, то машина
M также допускает на своем входе Mi, в противном случае работает бесконечно.
Таким образом, L(M) = Lne . “
Теорема. Язык Lne не является рекурсивным.
Доказательство. Построим функцию (алгоритм), сводящий универсальный язык Lu к языку Lne , т.е. вход (M,w) машины U преобразуем во вход машины M ’, допускающей язык Lne. Машина M ’моделирует машину M на входе w и если (M, w) Î Lu , то (M ’, x) Î Lu , где x произвольный вход машины M ’. В этом случае машина M’ допускает хотя бы одну цепочку, т.е. L(M’) ¹Æ и M ’Î Lne . Аналогично, в случае, если (M,w) Ï Lu , L(M ’ ) = Æ и M’ Î Lne . Схема машины M ’, построенной по (M,w) приведена на рис.
Рис.9.9
Машина M ’ по построению выполняет следующие действия:
1. Машина M ’строится по конкретной паре (M,w), имеюшей длину n,
тогда q0 ,…,qn состояния M ’ (где q0 - начальное состояние).
a) В состоянии qi (i=0,..,n-1) машина M ’ записывает (i+1)-й бит кода
(M,w) и переходит в состояние qi+1 , сдвигаясь вправо.
b) В состоянии q n , в случае необходимости, M ’сдвигается вправо и заполняет все непустые клетки (хвост x, если длина цепочки x боль- ше n) пробелами.
2. Когда M ’ достигает пробела с состоянии qn , она, используя похожий набор состояний, перемещает головку в левый конец ленты.
3. Используя дополнительные состояния M ’ моделирует универсальную машину U.
4. Если U допускает, то M ’допускает. Если U никогда не допускает, то M ’ никогда не допускает.
Из схемы работы машины видно, что если M допускает вход w, то M ’ допускает свой вход x, который первоначально был записан на ленте, следовательно, M ’ Î Lne . В противном случае, если M не допускает вход w, то M ’не допускает любой свой вход x, записанный на ленте, тогда M ’ Ï Lne. Таким образом, Lu сводимо к Lne с помощью алгоритма, который строит M’ по данным M и w. Поскольку, Lu не является рекурсивным, то Lne также не рекурсивен. “
Теперь известен и статус языка Le. Если бы Le был бы рекурсивно перечислимым, то по теореме и он, и его дополнение Lne были бы рекурсивными. Однако было доказано, что язык Lne не рекурсивен.
Теорема.Язык Le не является рекусивно перечислимым. “
