Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 89
Текст из файла (страница 89)
Для того чтобы отобразить переход М, У отыскивает на своей первой ленте переход 0'10'10" 10'10, у которого 0' есть состояние на ленте 3, а У вЂ” ленточный символ М, начинающийся с позиции на ленте 2, обозреваемой с/. Это переход, который М совершает на следующем шаге. Машина !/ должна выполнить следующие действия: а) изменить содержимое ленты 3 на 0", т.е.
отобразить изменение состояния М. Для этого У вначале заменяет все символы 0 на ленте 3 пустыми символами, а затем копирует 0" с ленты ! на ленту 3; б) заменить !У на ленте 2 символами О, т.е. поменять ленточный символ М. Ес! ли потребуется больше или меньше места (т.е./ ~ 1), то для управления пространством используются рабочая лента и техника переноса (см. раздел 8.6.2); в) переместить головку на ленте 2 в ту позицию слева или справа, в которой находится ближайший символ 1. При гл = 1 совершается сдвиг влево, а при т = 2 — вправо. Таким образом, У имитирует движение М влево или вправо.
5. Если Мне имеет перехода, соответствующего имитируемым состоянию и ленточному символу, то в п. 4 переход не будет найден. Таким образом, в данной конфигурации М останавливается, и то же самое должна делать У. 6. Если М попадает в свое допускающее состояние, то !/допускает. Этими действиями (/ имитирует работу М со входом в . !/ допускает закодированную па- ру (М, и) тогда и только тогда, когда М допускает и . 388 ГЛАВА 9. НЕРАЗРЕШИМОСТЬ Более эффективная универсальная МТ Машина Н, эффективно имитирующая М, т.е. не требующая сдвига ленточных символов, должна вначале определять число ленточных символов, используемых М.
Если число символов лежит в пределах от 2 до 2 — 1, то однозначно представить разь-1 личные ленточные символы можно с помошью 1г-битового двоичного кода. Каждой клетке М можно поставить в соответствие я клеток машины ~/. Для того чтобы упростить имитацию, можно переписать в машине Н данные переходы М и вместо описанного нами унарного кода переменной длины использовать бинарный код фиксированной длины. 9.2.4. Неразрешимость универсального языка Представим проблему, которая является РП, но не рекурсивной. Это язык 2,„.
Неразрешимость 2„(т.е. его нерекурснвность) во многих отношениях важнее, чем наш предыдуший вывод о том, что язык Ьа не является РП. Причина состоит в следующем. Сведением Т,„к другой проблеме Р можно показать, что алгоритма, решающего Р, не сушествует, независимо от того, является ли Р РП. Однако сведение 2,а к Р возможно лишь тогда, когда Р не является РП, поэтому Т,а не может использоваться при доказательстве неразрешимости проблем, которые являются РП, но не рекурсивными.
Вместе с тем, если нужно показать, что проблема не является РП, то можно использовать только Ть в то время как язык А„оказывается бесполезным, поскольку он являел~ся РП. Теорема 9.6. 2.„является РП, но не рекурсивным. Доказательство. В разделе 9.2.3 доказано, что язык А„является РП. Допустим, что 2.„ рекурсивен. Тогда по теореме 9.3 Х „(дополнение 2,„) — также рекурсивный язык, Но если сушествует МТ М, допускающая Х „, то, используя описанный ниже метод, можно построить МТ, допускающую Ь~. Поскольку нам известно, что Та не является РП, приходим к противоречию с предположением, что язык 2,„является рекурсивным. Проблема останова Проблема осталова машины Тьюринга считается подобной проблеме 2„; она также является РП, но не рекурсивной. В действительности, определенная А.
М. Тьюрингом машина допускала, не попадая в допускаюшее состояние, а останавливаясь. Для МТ М можно определить Н(М) как множество входов зг, на которых М останавливается независимо от того, допускает ли М вход ш. Тогда проблема останова состоит в определении множества таких пар (М, в ), у которых и принадлежит НГМ).
Это еще один пример проблемы!языка, которая является РП, но не рекурсивной. Предположим, что ЦМ) = Е „. На рис. 9.6 показано, как можно преобразовать МТ М в МТ М; которая допускает 2,а с помощью следующих действий. 9.2. НЕРАЗРЕШИМАЯ РП-ПРОБЛЕМА 389 Допустить Отаертнуь Рис. 9.б. Сведение Де к т'. 1. М'преобразует входную цепочку те в и!1!и. В качестве упражнения читатель может написать программу для выполнения этого шага на одной ленте. Однако легче это сделать, используя для копии и вторую ленту, и затем преобразовать двухленточную МТ в одноленточную.
2. М'имитирует М на новом входе. Если те есть и, в нашем перечислении, то М' определяет, допускает ли М, вход теь Поскольку Мдопускает Х „, то она допускает тогда и только тогда, когда М, не допускает и и т.е. когда и, принадлежит Т,е. Таким образом, М'допускает и тогда и только тогда, когда те принадлежит Те. Поскольку по теореме 9.2 машины М'не существует, приходим к выводу, что язык Т., не является рекурсивным. П 9.2.5. Упражнения к разделу 9.2 9.2.1.
Покажите, что проблема останова, т.е. проблема определения множества пар (М и), где Мостанавливается (допуская или нет) на входе те, является РП, но не рекурсивной. (См. врезку "Проблема останова" в разделе 9.2.4.) 9.2.2. Во врезке "Почему "рекурсивные"?" из раздела 9.2.1 говорилось о "рекурсивных функциях" как модели вычислимости, используемой наравне с машинами Тьюринга. В данном упражнении рассмотрим пример записи рекурсивных функций. Рекурсивная функция — это функция тт, определенная конечным набором правил. Каждое правило устанавливает значение функции Р для определенных аргументов; в правиле могут присутствовать переменные, неотрицательные целочисленные константы, функция прибавления единицы (зпссеззог), сама функция г" и выражения, построенные композицией перечисленных функций.
Например, функция Аккермана определяется следующим образом. 1. А(О,у) = 1 для всеху> 1. 2. А(1, 0) = 2. 3. А(х; О) = х + 2 для х > 2. 4. А(к+ 1,у+ 1) =А(А(х,уь1),у) длялюбыхх> 0 ну>0. ГЛАВА 9. НЕРАЗРЕШИМОСТЬ 390 Выполните следующее: а) (я) вычислите А(2, 1); б) (!) опишитеА(х, 2) как функцию отх; в) (!) вычислите А(4, 3). 9.2.3. Опишите неформально многоленточные машины Тьюринга, которые перечис- ляюа следующие множества целых чисел в том смысле, что, начав с пустых лент, они печатают на одной из лент цепочку 10ь10ч1..., представляющую множество (гь Гь " ): а) (я) множество квадратов целых чисел (1, 4, 9, ... ); б) множество простых чисел (2, 3, 5, 7, 11, ...
); в) (!!) множество всех таких 1, для которых М допускает иь Указание. Такие 1 невозможно генерировать в порядке возрастания. Причина состоит в том, что данный язык, который есть Х м является РП, но не рекурсивным. Такие языки по определению можно перечислить, но не в порядке возрастания. "Прием" с их перечислением состоит в том, чтобы смоделировать работу всех М; со входами и,. При этом мы не можем позволить какой-либо М, работать вечно, поскольку это помешает продолжать проверку лля других М, где ! ~ ). Поэтому мы вынуждены работать поэтапно, проверяя на к-м этапе лишь конечное множество машин М и ограничивая проверку каждой машины конечным числом шагов.
Таким образом, каждый этап проверки будет выполнен за конечное время. Поскольку для всякой МТ М, и всякого числа шагов з найдется такой этап, на котором будет промоделировано не менее з шагов М„то в конце концов мы обнаружим все Мь допускающие и„и перечислим номера й 9.2.4. (я) Пусть (,н (л ..., (ь — набор языков в алфавите Х, для которого верны следующие утверждения. 1.
С;Й(э~к) для всех 1~~, т.е. никакая цепочка не принадлежит сразу двум языкам. 2. (,, () Е, () " () Сь = Х, т.е. кажлая цепочка принадлежит одному из этих языков. 3. Все языки Еа где ! =- 1, 2, ..., 2, рекурсивно перечислимы. Докажите, что тогда каждый из этих языков рекурсивен. 9.2.5. (яЦ Пусть Е рекурсивно перечислим и Х ие является РП. Рассмотрим язык ь'= (Ом ) зг принадлежитЦ 0 (1и ) и не принадлежит Ц.
Можете ли вы наверняка сказать, что язык Е' или его дополнение являются ре- курсивными, РП или не-РП? Ответ обоснуйте. 9.2. НЕРАЗРЕШИМАЯ РП-ПРОБЛЕМА 9.2.б. (!) За исключением операции дополнения в разделе 9.2.2, свойства замкнутости рекурсивных и РП-языков пока не обсуждались. Выясните, замкнуты ли рекурсивные и/или РП-языки относительно перечисленных ниже операций: а) (в) объединение; б) пересечение; в) конкатенация; г) замыкание Клнни (звездочка); д) (в) гомоморфизм; е) обратный гомоморфизм. Обосновывая замкнутость, можно использовать неформальные, но достаточно понятные конструкции. 9.3.
Неразрешимые проблемы, связанные с машинами Тьюринга Статус языков /,„и /а относительно неразрешимости и рекурсивной перечислимости нам уже известен. Используем их для демонстрации других неразрешимых или не РП-языков. В доказательствах используется техника сведения. Все неразрешимые проблемы, которые рассматриваются вначале, связаны с машинами Тьюринга. Кульминацией данного раздела является доказательство "теоремы Райса".
В ней утверждается, что любое нетривиальное свойство МТ, зависящее лишь от языка, допускаемого машиной Тьюринга, должно быть неразрешимым. Материал раздела 9.4 позволяет исследовать некоторые неразрешимые проблемы, не связанные ни с машинами Тьюрин- га, ни с их языками.
9.3.1. сведения Понятие сведения было введено в разделе 8.1.3. В общем случае, если у нас есть алгоритм, преобразующий экземпляры проблемы Р, в экземпляры проблемы Р„которые имеют тот же ответ (да/нет), то говорят, что Р~ сводится к Р,. Доказательство такой сводимости используется, чтобы показать, что Р, не менее трудна, чем Р,. Таким образом, если Р~ не является рекурсивной, то и Р, не может быть рекурсивной. Если Р~ не является РП, то и Р, не может быть РП. Как уже упоминалось в разделе 8.1.3, чтобы доказать, что проблема Рз не менее трудна, чем некоторая известная Рь нужно свести Р, к Рь а не наоборот.
Как показано на,рис. 9.7, сведение должно переводить всякий экземпляр Р, с ответом "да" (позитивный) в экземпляр Р, с ответом "да", и всякий экземпляр Р~ с ответом "нет" (негативный) — в экземпляр Рз с ответом "нет". Отметим, что неважно, является ли каж- 392 ГЛАВА 9. НЕРАЗРЕШИМОСТЬ ямй экземпляр Р, образом одного или нескольких экземпляров Рь В действительности, вбычно лишь небольшая часть экземпляров Р, образуется в результате сведения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
