dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 86
Текст из файла (страница 86)
9.1 хотя бы в одном столбце. Поэтому дополнение диагонали не может быть характеристическим вектором никакой машины Тьюринга.9.1.4. Äîêàçàòåëüñòâî íåïåðå÷èñëèìîñòè LdРазвивая наши рассуждения о характеристических векторах и диагонали, формально докажем основной результат, касающийся машин Тьюринга, — МТ, допускающейязык Ld, не существует.Теорема 9.2. Язык Ld не является рекурсивно-перечислимым, т.е. не существует машины Тьюринга, которая допускала бы Ld.Доказательство. Допустим, что Ld = L(M) для некоторой МТ M.
Так как Ld — язык надалфавитом {0, 1}, M должна содержаться в построенной нами последовательности машин1Заметим, что в действительности эта таблица выглядит совсем не так, как на рисунке. Ееверхние строки должны быть заполнены нулями, поскольку все небольшие целые числа не могутбыть правильными кодами МТ.9.1. ÍÅÏÅÐÅ×ÈÑËÈÌÛÉ ßÇÛÊСтр. 381381Тьюринга, поскольку эта последовательность содержит все МТ с входным алфавитом {0, 1}.Следовательно, в ней есть, по крайней мере, один код машины M, скажем, i, т.е. M = Mi.Выясним теперь, принадлежит ли wi языку Ld.• Если wi принадлежит Ld, то Mi допускает wi. Но тогда (по определению Ld) wi не принадлежит Ld, так как Ld содержит лишь такие wj, для которых Mj не допускает wj.• Точно так же, если wi не принадлежит Ld, то Mi не допускает wi.
Но тогда (по определению Ld) wi принадлежит Ld.Поскольку wi не может одновременно и принадлежать, и не принадлежать Ld, приходим кпротиворечию с нашим предположением о том, что M существует. Таким образом, Ld неявляется рекурсивно-перечислимым языком. 9.1.5. Óïðàæíåíèÿ ê ðàçäåëó 9.19.1.1.Запишите следующие цепочки:а) (∗) w37;б) w100.9.1.2.Запишите один из возможных кодов машины Тьюринга, изображенной на рис.
8.9.9.1.3.(!) Ниже приводятся определения двух языков, похожих на Ld, но все же отличных от него. Используя операции типа диагонализации, покажите, что каждыйиз них не может допускаться никакой машиной Тьюринга. Отметим, что приэтом нужно использовать не диагональ, а какую-то другую бесконечную последовательность элементов матрицы, изображенной на рис. 9.1:а) (∗) множество всех wi, для которых M2i не допускает wi;б) множество всех wi, для которых Mi не допускает w2i.9.1.4.(!) Машины Тьюринга, рассмотренные до сих пор, имели входной алфавит{0, 1}.
Допустим, мы хотели бы приписать целые числа всем машинам Тьюринга, независимо от их входного алфавита. Это, вообще говоря, невозможно. Ведьв то время, как имена состояний или рабочие символы на ленте (которые не являются входными), произвольны, каждый входной символ имеет значение. Например, языки {0n1n | n ≥ 1} и {anbn | n ≥ 1} похожи, однако не совпадают и допускаются разными МТ. Допустим тем не менее, что у нас есть бесконечноемножество символов {a1, a2, …}, из которого выбираются все алфавиты МТ.Покажите, как можно приписать целые числа всем МТ, входной алфавит которых является конечным подмножеством этих символов.9.2.
Íåðàçðåøèìàÿ ÐÏ-ïðîáëåìàИтак, мы убедились, что существует проблема (язык диагонализации Ld), которая не допускается никакой машиной Тьюринга. Наша следующая цель — уточнить структуру ре382Стр. 382ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜкурсивно-перечислимых языков (РП-языков), т.е. допустимых машинами Тьюринга, разбивих на два класса. В первый класс войдут языки, которым соответствует то, что обычно понимается как алгоритм, т.е. МТ, которая не только распознает язык, но и сообщает, чтовходная цепочка не принадлежит этому языку. Такая машина Тьюринга в конце концоввсегда останавливается независимо от того, достигнуто ли допускающее состояние.Второй класс языков состоит из тех РП-языков, которые не допускаются никакоймашиной Тьюринга, останавливающейся на всех входах.
Эти языки допускаются несколько неудобным образом: если входная цепочка принадлежит языку, то мы в концеконцов об этом узнаем, но если нет, то машина Тьюринга будет работать вечно. Поэтомуникогда нельзя быть уверенным, что данная входная цепочка не будет когда-нибудь допущена. Примером языка данного типа, как будет показано ниже, является множествотаких закодированных пар (M, w), в которых МТ M допускает вход w.9.2.1. Ðåêóðñèâíûå ÿçûêèЯзык L называется рекурсивным, если L = L(M) для некоторой машины Тьюринга M,удовлетворяющей следующим условиям.1.Если w принадлежит L, то M попадает в допускающее состояние (и, следовательно,останавливается).2.Если w не принадлежит L, то M в конце концов останавливается, хотя и не попадаетв допускающее состояние.МТ этого типа соответствует интуитивному понятию “алгоритма” — правильно определенной последовательности шагов, которая всегда заканчивается и приводит к некоторому ответу.
Если мы рассматриваем язык L как “проблему”, то проблема L называетсяразрешимой, если она является рекурсивным языком. В противном случае проблема называется неразрешимой.Существование алгоритма зачастую важнее, чем наличие некоторой МТ, решающейданную проблему. Как упоминалось ранее, машины Тьюринга, которые могут не останавливаться, не дают информации, необходимой для утверждения, что цепочка не принадлежит языку, т.е. они “не решают проблему”. Таким образом, разделение проблем иязыков на разрешимые (для них существует алгоритм решения) и неразрешимые частоважнее, чем разделение на рекурсивно перечислимые (для них существует МТ какоголибо типа) и неперечислимые (для них вообще не существует МТ).
На рис. 9.2 представлено соотношение трех классов языков.1.Рекурсивные языки.2.Языки, которые рекурсивно перечислимы (РП), но не рекурсивны.3.Неперечислимые (не-РП) языки.На рисунке указаны правильные положения не РП-языка Ld и “универсального языка” Lu,который, как мы вскоре докажем, является РП, но не рекурсивным.9.2. ÍÅÐÀÇÐÅØÈÌÀß ÐÏ-ÏÐÎÁËÅÌÀСтр. 383383РекурсивныеРП,нонерекурсивныеНеРПРис. 9.2. Соотношение рекурсивных,неперечислимых и РП-языковÏî÷åìó “ðåêóðñèâíûå”?Современные программисты знакомы с понятием рекурсивной функции. Остаетсянепонятным, что общего между рекурсивными функциями и машинами Тьюринга,которые всегда останавливаются. Еще хуже, что нерекурсивными, или неразрешимыми, называются языки, которые не распознаются никаким алгоритмом, хотя под“нерекурсивными” мы привыкли понимать вычисления настолько простые, что онине требуют обращений к рекурсивным функциям.Термин “рекурсивный” как синоним слова “разрешимый” возник в период развитияматематики, предшествовавший появлению компьютеров.
В качестве понятия вычисления обычно использовались формализмы, основанные на рекурсии (но не итерацииили цикле). В этих системах понятий (не рассматриваемых здесь) было нечто от вычислений в таких языках функционального программирования, как LISP или ML. Вэтом смысле выражение “проблема рекурсивна” означало, что она “проста настолько,что можно записать рекурсивную функцию, которая всегда приводит к ее решению законечное число шагов”. И в наши дни применительно к машинам Тьюринга этот термин имеет в точности тот же смысл.Термин “рекурсивно-перечислимый” — из того же семейства понятий. С помощьюнекоторой функции элементы языка можно выписать в некотором порядке, т.е.“перечислить” их.
Языки, элементы которых можно перечислить в некотором порядке, — это именно те языки, которые допускаются некоторой МТ (возможно, работающей бесконечно на недопустимых входах).384Стр. 384ÃËÀÂÀ 9. ÍÅÐÀÇÐÅØÈÌÎÑÒÜ9.2.2. Äîïîëíåíèÿ ðåêóðñèâíûõ è ÐÏ-ÿçûêîâДля доказательства того, что некоторый язык принадлежит второму кольцу нарис. 9.2 (т.е.
является РП, но не рекурсивным), часто используется дополнение этогоязыка. Покажем, что рекурсивные языки замкнутыотносительно дополнения. Поэтому,__L — нет, то L не может быть рекурсивным.если язык L является РП, а его дополнение__Если бы L был рекурсивным, то L также был бы рекурсивным, а следовательно, и РП.Докажем это важное свойство замкнутости рекурсивныхязыков.__Теорема 9.3.
Если L — рекурсивный язык, то язык L также рекурсивен.Доказательство. Пусть L = L(M) для некоторой всегда останавливающейся МТ M.__Согласно схеме на рис. 9.3 построим МТ M , у которой L = L( M ), т.е. M ведет себятак же, как и M; изменения касаются лишь допускающих состояний.1.Допускающие состояния M становятся недопускающими состояниями M , неимеющими переходов, т.е. в этих состояниях M останавливается, не допуская.2.M имеет новое допускающее состояние r, из которого нет переходов.3.Для каждой комбинации из недопускающего состояния и ленточного символа M, вкоторой M не имеет перехода (т.е. останавливается, не допуская), добавляется переход в допускающее состояние r.ДопуститьДопуститьОтвергнутьОтвергнутьРис.
9.3. Строение МТ, допускающей дополнение рекурсивного языкаПоскольку M всегда останавливается, то всегда останавливается и M . Крометого, M__допускает множество именно тех цепочек, которые не допускаются M, т.е. L . С дополнениями языков связан еще один важный факт. Он еще больше ограничиваетобласть на диаграмме (см. рис. 9.2), в которую могут попасть язык и его дополнение.
Этоограничение утверждается следующей теоремой.Теорема 9.4. Если язык L и__его дополнение являются РП, то L рекурсивен. Отметим,что тогда по теореме 9.3 язык L также рекурсивен.Доказательство. Доказательство представлено на рис. 9.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
