Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 88
Текст из файла (страница 88)
1. Рекурсивные языки. 2. Языки, которые рекурсивно перечислимы (РП), но не рекурснвны. 3. Неперечислимые (не-Р)Т) языки. На рисунке указаны правильные положения нс РП-языка Ев и "универсального языка" 2.„, который, как мы вскоре докажем, является РП, но не рекурсивным. 383 9.2. НЕРАЗРЕШИМАЯ РП-ПРОБЛЕМА Рис. 9 2.
Соопыоыение рекзрсивннсз, неперенисяииык и РП-языков Почему "рекурсивные"? Современные программисты знакомы с понятием рекурсивной функции. Остается непонятным, что общего между рекурсивными функциями и машинами Тьюринга, которые всегда останавливаются. Еще хуже, что нерекурсивными, илн неразреши- мыми, называются языки, которые не распознаются никаким алгоритмом, хотя под "нерекурсивными" мы привыкли понимать вычисления настолько простые, что они не требуют обращений к рекурсивным функциям. Термин "рекурсивный" как синоним слова "разрешимый" возник в период развития математики, предшествовавший появлению компьютеров.
В качестве понятия вычисления обычно использовались формализмы, основанные на рекурсии (но не итерации или цикле). В этих системах понятий (не рассматриваемых здесь) было нечто от вычислений в таких языках функционального программирования, как злбр или МЕ.
В этом смысле выражение "проблема рекурсивна" означало, что она "проста настолько, что можно записать рекурсивную функцию, которая всегда приводит к ее решению за конечное число шагов". И в наши дни применительно к машинам Тьюринга этот тер- мин имеет в точности тот же смысл. Термин "рекурсивно-перечислимый" — из того же семейства понятий. С помощью некоторой функции элементы языка можно выписать в некотором порядке, т.е. 'перечислить" их. Языки, элементы которых можно перечислить в некотором порядке, — это именно те языки, которые допускаются некоторой МТ (возможно, работающей бесконечно на недопустимых входах). ГЛАВА 9.
НЕРАЗРЕШИМОСТЬ 384 9.2.2. Дополнения рекурсивных и РП-языков Для доказательства того, что некоторый язык принадлежит второму кольцу на рис, 9,2 (т.е. является РП, но не рекурсивным), часто используется дополнение этого языка. Покажем, что рекурсивные языки замкнуты относительно дополнения. Поэтому, если язык Х является РП, а его дополнение Х вЂ” нет, то Ь не может быть рекурсивным. Если бы Х был рекурсивным, то Х также был бы рекурсивным, а следовательно, и РП.
Докажем это важное свойство замкнутости рекурсивных языков. Теорема 9.3. Если Х вЂ” рекурсивный язык, то язык Х также рекурсивен. Доказательство. Пусть Х = ЦМ) для некоторой всегда останавливающейся МТ М. Согласно схеме на рис. 9.3 построим МТ М, у которой Х = Ц М ), т.е. М ведет себя так же, как и М„изменения касаются лишь допускающих состояний. Е Допускающие состояния М становятся недопускаюшими состояниями М, не имеющими переходов, т.е. в этих состояниях М останавливается, не допуская. М имеет новое допускающее состояние е, из которого нет переходов. 3. Для каждой комбинации из недопускающего состояния и ленточного символа М, в которой М не имеет перехода (т.е.
останавливается, не допуская), добавляется пере- ход в допускающее состояние г. Допустить Отвергнуть Рис. 9.3 Строение МЕ допускающей дополнение рекурсияного языка Поскольку М всегда останавливается, то всегда останавливается и М . Кроме того, М допускает множество именно тех цепочек, которые не допускаются М, т.е. Х .
ь.1 С дополнениями языков связан еще один важный факт. Он еще больше ограничивает область на диаграмме (см. рис. 9.2), в которую могут попаст.ь язык и его дополнение. Это ограничение утверждается следующей теоремой. Теорема 9.4. Если язык Х и его дополнение являются РП, то Х рекурсивен. Отметим, что тогда по теореме 9.3 язык Х также рекурсивен.
Доказательство. Доказательство представлено на рис. 9.4. Пусть Е = Е (М,) и Х = ЦМт). Параллельная работа машин имитируется МТ М. Чтобы эта модель стала простой и очевидной, можно взять МТ с двумя лентами и затем преобразовать ее в одно- ленточную. Одна из них имитирует ленту Мь а вторая — ленту Мз. Состояния М, и Мз являются компонентами состояния М.
Если вход и машины М принадлежит Ц то М, в конце концов попадает в допускающее состояние; тогда М допускает и останавливается. Когда же в допускающее со- 9.2. НЕРАЗРЕШИМАЯ РП-ПРОБЛЕМА 385 стояние попадает Мз, М останавливается, не допуская. Таким образом, М останавливается при любом входе, и ЦМ) — это в точности Е. Отсюда заключаем, что язык Е— рекурсивный. С) Допустить Отвергнуть Рис. 9.4. Моделирование двух МГ, одна из которых допускает некоторый язык, а вторая — еео дополнение Теоремы 9.3 и 9.4 можно объединить следующим образом. Из девяти способов расположения языка Е и его дополнения Х (см. диаграмму на рис. 9.2) возможны лишь следующие четыре'.
1. Оба языкаЕ и Х рекурсивны, т.е. оба они находятся во внутреннем кольце. 2. Нн Е, ни Е не являются РП, т.е. оба они находятся во внешнем кольце. Е является РП, но не рекурсивным, и Х не является РП, т.е. один находится в среднем кольце, а другой — во внешнем. Е является РП, но не рекурсивным, и Е не является РП, т.е. Е и Е меняются местами по отношению к случаю 3.
В качестве доказательства отметим, что теорема 9.3 исключает возможность того, что один из языков (Е или Е ) является рекурсивным, а второй принадлежит какому-либо из оставшихся классов. При этом теорема 9.4 исключает возможность того, что оба языка являются РП, но не рекурсивными. Пример 9.5. Рассмотрим язык Ет который, как мы знаем, не является РП. Поэтому язык Е в не может быть рекурсивным. Однако Е в может быть либо не-РП, либо РП, но не рекурсивным. На самом деле верно последнее.
Е в есть множество цепочек и ь допускаемых соответствующими М. Этот язык похож на универсальный язык Е„, состоящий из всех пар 1М, и), где М допускает и, который, как мы покажем в разделе 9.2.3, является РП. Точно так же можно показать, что Е в является РП. П 2 По существу, их всего три. — Прим. ред.
ГЛАВА 9. НЕРАЗРЕШИМОСТЬ 386 9.2.3. Универсальный язык Б разделе 8.6.2 уже неформально обсуждалось, как можно использовать машину Тьюринга в качестве модели компьютера с загруженной в него произвольной программой. Иными словами, отдельно взятая МТ может использоваться как "компьютер с записанной программой", который считывает свою программу и данные с одной или нескольких лент, содержащих входную информацию. В данном разделе будет формализована идея того, что машина Тьюринга является представлением программы, записанной в память компьютера. Универсальный язык Т.„определяется как множество двоичных цепочек, которые являются кодами (в смысле определения из раздела 9.!.2) пар (М, и), где М вЂ” МТ с двоичным входным алфавитом, а те —. цепочка из (О+1), принадлежащая 7.(М).
Таким образом, 7 — это множество цепочек, представляющих некоторую МТ и допускаемый ею вход. Покажем, что существует МТ (т, которую часто называют универсальной машиной Тьюринга, для которой Т,„= Ц(т). Поскольку входом (/ является двоичная цепочка, то в действительности (7 — это некоторая М в списке машин Тьюринга с двоичным входом (см. раздел 9. 1.2).
Проще всего (/ описывается как многоленточная машина Тьюринга в стиле рис. 8.22. В машине (7 переходы М вначале хранятся на первой ленте вместе с цепочкой н. Вторая лента используется для моделирования ленты машины М, в том же формате, что и у кода М. Таким образом, ленточный символ Х машины М кодируется как О', а коды разделяются одиночными !. На третью ленту (5 записывается состояние М, причем состояние 9, представляется в виде т нулей. Схема (7 представлена на рис.
9.5. Вход Лентам Состоянием 000 -. ОВВ Рабочая лента Рис. 9.5. Структура универсальной машины Тьюринга 9.2. НЕРАЗРЕШИМАЯ РП-ПРОБЛЕМА 387 Машина У производит следующие операции. 1. Исследует вход для того, чтобы убедиться, что код М является правильным кодом МТ. Если это не так, У останавливается, не допуская.
Это действие корректно, поскольку неправильные коды по договоренности представляют МТ без переходов, а такие МТ не допускают никакого входа. 2. Записывает на вторую ленту код входной цепочки ж. Таким образом, каждому символу 0 из и на второй ленте ставится в соответствие цепочка 10, а каждой 1 — цепочка 100. Отметим, что пустые символы, которые находятся на ленте самой М и представляются цепочками вида 1000, на этой ленте появляться не будут. Все клетки, кроме занятых символами цепочки и, будут заполняться пустыми символами машины У.
Но при этом !/знает, что если она ищет имитируемый символ М и находит свой собственный пустой символ, то она должна заменить его последовательностью 1000, имитирующей пустой символ М. 3. На третьей ленте записывает О, т.е. начальное состояние М, и перемещает головку второй ленты У в первую имитируемую клетку. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
