Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 73
Текст из файла (страница 73)
2. Затем Н; имитирует Нл но вместо чтения из Р или Р программа Н, читает из копии в массиве А. Для запоминания мест в Р и 1, до которых дочитала Нь Нз может содержать два курсора, отмечающих позиции в А. уев веще, еосз а Рис. 8.5. Нз ведет себя, как Нь но использует вход Р в качестве как Р, так и 1 Теперь все готово для доказательства того, что Н, не существует. Таким образом, не существует Н~ и, аналогично, Н. Для того чтобы в этом убедиться, нужно представить себе, что делает Нл когда получает себя в качестве входа (рис. 8.6). Напомним, что Нн получив некоторую программу Р на вход, печатает уен, если Р печатает )зе11о, ыох1с), получая себя в качестве входа. Кроме того, Н~ печатает )зе11о, ног1с1, если Р, получив себя на вход, не выдает пе11о, иок1с! в качестве начала своего выхода.
Функция па11ос сисгемы 13г!!Х распределяет блок памяги, размер которого задаегся в ее вьпове. Эга функция используегся, когда нужный размер памяти невозможно определить до начала выполнения программы, как и при чтении входа произвольной ллины. Обычно па11ос вьпывается несколько рп по мере того, как возрасгают объем прочитанного входа и потребность в памяти. 324 ГЛАВА 8.
ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА уев Ке11о, вос1а Рис. В.б. Чта делает Нь аалучая себя в качестве входа? Предположим, что Нз в рамке (см. рис. 8.6) печатает уеи. Тогда Нз в рамке говорит о своем входе Нь что Н„получая себя в качестве входа, вьщает вначале 1эе11о, зчог1с1 Но мы попив что предположили, что выход Нз начинается текстом уеи, а не 1зе11о, гчог1сь Таким образом, получается, что выходом программы в рамке (см. рис. 8.6) является па уев, а 1зе11о, зчог1с1, поскольку возможно либо одно, либо другое. Но если Н,, получая себя на вход, печатает 1эе11о, хог1с$, то выходом программы в рамке на рпс. 8.6 должно быть уеи.
Каким бы ни был предполагаемый выход Нь доказано, что она печатает противоположное. Описанная ситуация противоречива, и мы приходим к выводу, что Н, не может существовать. Это опровергает предположение о существовании Н. Таким образом, доказано, по ни одна программа Н не может сказать, печатает ли данная программа Р со входом 1 текст 1уе11о, зчог1с1. 8,1,3. Сведение одной проблемы к другой Печатает ли данная программа в начале своего выхода текст 1зе11о, хог1с1? Мы уже знаем, что ни одна компьютерная программа этот вопрос разрешить не может. Проблема, которую нельзя разрешить с помощью компьютера, называется неразрешимой.
Формальное определение "неразрешимого" будет дано в разделе 9.3, а пока этот термин используется неформально. Предположим, что нам нужно определить, разрешима ли некоторая новая проблема. Мы можем попытаться написать программу для ее разрешения, но, если нам непонятно, как это сделать, мы можем попробовать доказать, что такой прп раммы не существует. Перюрешимость новой проблемы можно было бы доказать аналогично тому, как это было сделано для проблемы "пейо, зчог!г!": предположить, что программа разрешения существует, и построить противоречивую программу, которая должна делать одновреиепво две взаимно исключающие вещи, как программа Нь Однако если у нас есть проблема, неразрешимость которой установлена, то нам не обязательно вновь доказывать пропворечивость.
Достаточно показать, что если новая проблема имеет решение, то его кожно использовать для разрешения уже известной неразрешимой проблемы. Такой вщход представлен на рис. 8.7 и называется сведением Р! к Р . Предположим, нам известно, что проблема Р, неразрешима, а Р, — новая проблема, шрпзрешимость которой нужно доказать. Допустим, что существует программа, которая 3,1.
ЗАДАЧИ, НЕ РЕШАЕМЫЕ КОМПЬЮТЕРАМИ 325 представлена ромбом с отметкой "разрешить" !см, рис. 8.7) и печатает уев или по в за- висимости от того, принадлежит или нет ее входной экземпляр проблемы Рз языку этой проблемы.' — ш. уев ЭкземпляР Р, Экземпляр — в Рз пс Рис, 8. 7. Если бы можно была разрешить проблему Рь та ее решение мы мазки бы использовать для разрешения праблемы Р1 Для доказательства неразрешимости проблемы Р, нужно создать алгоритм, который представлен квадратом на рис. 8.7 и преобразует любой экземпляр Рз в экземпляр Рь причем их ответы всегда совпадают. Имея такое преобразование, проблему Рз можно разрешить следующим образом.
1. Применить алгоритм построения к данному экземпляру проблемы Рь т.е. к строке ш, которая может принадлежать нли не принадлежать языку Р,, и получить строку х. 2. Проверить, принадлежит ли х языку Рз, и перенести ответ на ш и Рз. Действительно ли компьютер может делать все это? Если присмотреться к программе, представленной на рис. 8.2, можно спросить, действительно ли она находит контрпрнмеры к великой теореме Ферма. Как-никак, целые числа в типичном компьютере имеют всего 32 бит, и если самый маленький контрпример содержит числа, измеряемые биллионами, то произойдет ошибка пере- ' Напомним, чтп'проблема в действительности представляет собой язык. Говоря о проблеме разрешения, приводят пи данные программа и вход к печати !зе11о, ыог1с!.
мы в действительности говорим о цепочках, пбриопзнных С-программами и их входными данными. Это множество цепочек является языком нзд алфавитом из символов АЗСН. 326 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА Пример 8.1. Применим описанный метод для доказательства, что вопрос "вызывает ли когда-нибудь программа Д с данным входом у функцию Еоо" неразрешим. Заметим, что в Д может не быть функции Еоо, и в этом случае задача решается просто.
Однако она становится сложной, если Д имеет функцию Еоо, но с у на входе может как достичь, так и не постичь вызова Еоо. Поскольку нам известна только одна неразрешимая проблема, роль Р, на рис. 8.7 играет проблема 'Ъе!!о, зиог1с!". В качестве Р, выступает описанная только что проблема "са!!з-7оа". Предположим, что существует программа разрешения этой проблемы. Наша задача — построить алгоритм, который преобразует проблему "пе11о, зног!зГ' в проблему "са11з-Гоо". полнения, прежде чем отыщется решение.
И вообще, компьютер со ! 28 Мбайт оперативной памяти и 30-гигабайтным диском имеет "всего" 256'~"~~~~~ состояний и является, таким образом, конечным автоматом. Однако рассмотрение компьютера как конечного автомата (или мозга как конечного атоыата, откуда, кстати, происхолит идея КА) непродуктивно. Число состояний насюлько велико, а пределы настолько размыты, что прийти к каким-либо полезным заключениям невозможно.
В действительности, есть все причины поверить в то, что прв желании множество состояний компьютера можно расширять до бесконечности. Например, целые числа можно представить в виде связанных списков цифр произвольной длины. Если память исчерпывается, программа печатает запрос на замену жлолиенного диска новым, пустым. И такие запросы могут повторяться по мере надобности сколько угодно раз. Такая программа будет намного сложнее, чем приведенная на рис. 82, но все равно мы сможем ее написать. Подобные приемы позволят любой другой программе обойти ограничения на размер памяти, величину целых чисел я другие параметры.
Итак, имея программу Д и ее входу, мы должны построить программу Л и ее вход х ткг„чтобы Я со входом г вызывала 1оо тогда и только тогда, когда Д со входом у печапкт бе11о, ног 1ой Конструкция проста. 1 Если Д имеет вызываемую функцию 1оо, переименовать ее и все ее вызовы. Очевидно, новая программа Д, выполняет то же самое, что и Д. 1 Добавить в Д> функцию боо. Эта функция не делает ничего и не вызывается. Полученная программа называется Дл 1 Изменить Д, так, чтобы первые 12 символов ее печати запоминались в глобальном массиве А. Пусть полученная программа называется Дь 4.
Изменить Д, так, чтобы после каждого выполнения инструкции печати с использованием массива А проверялось, напечатано ли не менее 12 символов, и если так, то яе образуют ли первые 12 символов текст Ие11о, ног1б. В этом случае вызвать новую функцию боо, добавленную в п. 2. Полученная программа есть й, а ее вход з совпадает с у.
Предположим, что Д со входом у печатает Ие11о, хог1с4 в качестве начала своего выхода. Тогда построенная 41 вызывает 1оо. Однако если Д со входом у не печатает сначкка Не11о, хог1б, то Я со входом х никогда не вызывает боо. Если можно решить, выливает ли Я со входом х функцию Еоо, то можно и решить, печатает ли Д со входом у аачкла Ье11о, хог1с1 Поскольку нам известно, что алгоритма решения проблемы 'Ъе11о, хог1с(" нет, и все 4 этапа построения Я по Д можно выполнить, отредактирою код, то предположение о том, что программа разрешения проблемы "сайз4оо" сущектнует, ложно. Такой программы нет, и данная проблема неразрешима.
П 8.1. ЭАДАЧИ, НЕ РЕШАЕМЫЕ КОМПЬЮТЕРАМИ Направление сведения является важным Обычная ошибка — пытаться доказывать неразрешимость проблемы Р, путем сведения ее к известной неразрешимой проблеме Р„т.е. доказывать утверждение "если Р~ разрешима, то Р, разрешима". Это утверждение, безусловно, истинное, бесполезно, поскольку предпосылка "Р~ разрешима" ложна. Единственный путь доказать, что новая проблема Р, неразрешима, состоит в том, чтобы свести к ней уже известную неразрешимую проблему, т.е. доказать утверждение "если Р~ неразрешима, то Р~ неразрешима*'. Поскольку неразрешимость Р, уже установлена, приходим к выводу, что Р, неразрешима.
8.1.4. Упражнения к разделу 8.1 Сведите проблему 'Ъе11о, мог1с1" к каждой из следующих проблем. Используйте неформальный стиль данного раздела для описания правдоподобных преобразований программ и не беспокойтесь о реальных пределах размеров файла или памяти в компьютерах: 8.1.1. а) Пв) по данной программе и ее входу определить, останавливается ли она когда-нибудь, т.е.
не зацикливается ли при данном входе; б) по данной программе и ее входу определить, печатает ли она вообще чтонибудь; в) (!) по данным двум программам и входу определить, порождают ли они один и тот же выход при данном входе. 8.2. Машина Тьюринга 328 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА Цель теории неразрешимых проблем состоит не только в том, чтобы установить существование таких проблем (что само по себе не просто), но также в том, чтобы обеспечить программистов информацией, какие задачи программирования можно решить, а какие нельзя.
Теория также имеет огромное практическое значение, когда рассматриваются проблемы, которые хотя и разрешимы, но требуют слишком большого времени для их решения 1см. главу 10). Эти проблемы, называемые "трудно разрешимыми", или "труднорешаемыми", подчас доставляют программистам и разработчикам систем больше хлопот, чем неразрешимые проблемы. Причина в том, что неразрешимые проблемы редко возникают на практике, тогда как трудно разрешимые встречаются каждый день. Кроме того, они часто допускают небольшие модификации условий или эвристические решения. Таким образом, разработчику постоянно приходится решать, относится ли данная проблема к классу труднорешаемых и что с ней делать, если это так.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
