Теперь можно представить таблицу, у которой по горизонтали стоят номера всех цепочек, а по вертикали номера всех машин Тьюринга
(все натуральные числа), а на пересечении i-й строки и j-го столбца стоит 1, если машина Mi допускает цепочку ωj, и 0 – если не допускает.
Числа по главной диагонали показывают, допускает ли машина Mi цепочку ωi. Построим язык Ld такой, что ωi ∈ Ld ↔ ωi ∉ Mi.
Ld называют языком диагонализации. Очевидно, что он не попадает в перечисление языков машин Тьюринга, т. е. нет допускающей его машины Тьюринга.
Теорема. Язык Ld не является рекурсивно перечислимым, т. е. не существует допускающей его машины Тьюринга.
Доказательство. Допустим противное, что существует машина Mi, допускающая язык Ld, так что Ld = L(Mi). Теперь, если Mi допускает ωi,
то ωi ∈L(Mi) = Ld, однако согласно определению языка Ld, ωi ∉ Ld ; если Mi не допускает ωi, т. е. ωi ∉ L(Mi) = Ld, но по определению языка Ld, ωi ∈ Ld. Откуда ωi ∈ Ld ↔ ωi ∉ Ld, что образует противоречие. Таким образом, не существует машины, допускающей язык Ld , а следовательно, язык диагонализации Ld не является рекурсивно перечислимым языком.
Рекурсивные языки. Неразрешимая РП – проблема.
Язык 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(M1) и L =L(M2). Возьмем машину Тьюринга M с двумя лентами, имитирующими соответственно машины M1 и M2.
Пусть вход ω ∈ L, тогда M1 допускает ω, а машина M допускает и останавливается; в противном случае машина M останавливается, не допуская. Таким образом, машина M останавливается на любом входе и L= L(M), т. е. L рекурсивный язык.
Следствие. Из девяти способов соотношений языков L и L’ возможны следующие четыре:
1. Оба языка L и L’ рекурсивны.
2. Ни L, ни L’ не являются рекурсивно перечислимыми.
L является рекурсивно перечислимым, а L’ не рекурсивно перечислим. L’ является рекурсивно перечислимым, а L не рекурсивно перечислим.Универсальный язык Lu определяется как множество цепочек в алфавите {0,1}, являющихся кодами упорядоченных пар (M, ω), где M - машина Тьюринга с входным алфавитом {0,1} и ω - цепочка из {0,1}*, принадлежащая L(M). Код упорядоченной пары (M,ω) представляется кодом машины M, отделенным 111 от кода цепочки ω. Другими словами, язык Lu - это множество цепочек, кодов упорядоченных пар (M,ω), представляющих машину Тьюринга и допускаемый ею вход. Покажем, что существует машина Тьюринга U, называемая универсальной машиной, для которой Lu = L(U).
Опишем машину U в виде многоленточной машины Тьюринга, имитирующей работу машины M на входе ω, когда сама она получает на вход цепочку, представляющую код упорядоченной пары (M,ω).
Пусть на 1-й ленте машины U хранятся переходы машины M вместе с входом ω; на 2-й ленте – двоичный код машины M; на 3-й - состояние машины M; 4-ая - рабочая лента.
Машина U производит следующие операции:
1. Исследует вход, и если код M правильный, записывает на 2-ю ленту код входной цепочки ω. Для неправильных кодов M машина U не допускает никакого входа.
На 2-й ленте все клетки, кроме занятых кодом входа ω, заполняются символом Λ, представляемым как 1000. На 3-й ленте записывается 0, т. е. начальное состояние q0 машины M, и считывающая головка обозревает первый символ кода ω. Чтобы отобразить переход машины M, машина U отыскивает его на первой ленте, например, 0i 10j 10k 10l 10m (m=1,2,3 – кодирует R, L,S),и выполняет следующие действия:
изменяет содержимое 3-ей ленты на 0k; заменяет 0j на второй ленте на 0l ; перемещает головку на 2-й ленте согласно 0m. Если M не имеет перехода, то M останавливается, и U останавливается. Если M попадает в допускающее состояние, то U допускает.Таким образом, U допускает вход (M,ω) тогда и только тогда, когда M допускает ω.
Неразрешимость универсального языка. Проблема останова.
Существуют рекурсивно перечислимые, но не рекурсивные языки, один из таких языков Lu. Сведением Lu к проблеме P можно доказать, что P не имеет алгоритма.
Теорема. Язык Lu рекурсивно перечислим, но не рекурсивен.
Доказательство. Была доказана рекурсивная перечислимость языка Lu. Допустим, что Lu рекурсивен, тогда по теореме язык Lu рекурсивен и существует допускающая его машина M, т. е. Lu = L(M). Преобразуем M
в машину M ’, допускающую Lu : если вход ω есть ωi, т. е. код машины Mi, то M ’ определяет, допускает ли Mi вход ωi. Поскольку M допускает
Lu, то M допускает ωi, если Mi не допускает ωi , т. е. когда ωi ∈ Ld.
Таким образом, M ’ допускает ω тогда и только тогда, когда ω∈ Ld.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
