Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 72
Текст из файла (страница 72)
проблем, которые не может решить нн один компьютер. Мы покажем, что многие просто формулируемые задачи в действительности неразрешимы. Примером может служить распознавание, является лн данная грамматика неоднозначной, н ряд таких примеров будет продолжен. 8.1. Задачи, не решаемые компьютерами Цель этого раздела — с помощью С-программнровання неформально доказать, что существуют задачи, которые невозможно решить, используя компьютер. Мы рассмотрим частную задачу распознавания, является лн текст Ье11о, ыог1с1 первым, что печатает С-программа, Можно подумать, будто имитация любой программы всегда позволит сказать, что она делает, однако в реальности нам придется "бороться" с программамн, которые работают невообразимо долго, прежде чем что-ннбудь вывести на печать.
Эта про- блема — незнание момента, в который что-то произойдет, если вообще произойдет,— является основной причиной нашей неспособности распознать, что делает программа. Однако доказательство того, что не существует алгоритма решения указанной задачи распознавания, весьма сложно и требует определенного формализма. В этом разделе предпочтение отдается формальным доказательствам, а не интуиции.
8.1.1. Программы печати „НеПо, мгог!да На рис. 8.! показана первая С-программа, представленная в классической книге Кернигана и Ритчи. Несложно обнаружить, что данная программа печатает )зе11о, ыох1с! ! и останавливается. Она настолько прозрачна, что обычно знакомство с языками программирования начинается демонстрацией того, как на этих языках написать программу печати )те11о, игох1с). таугг 1) ! ргйпгй(")зе11о, чгох1с)1п") Рис. 8.!. Программа Керяигаиа и Ритчи, приветствующая мир Однако есть и другие программы, которые тоже печатают Ье11о, игох1с), причем отнюдь не очевидно, что они делают именно это. На рис. 8.2 представлена еще одна программа, которая, возможно, печатает )зе11о, ыох1с). Она получает на вход и и ищет положительные целые решения уравнения х" + у" = х". Если находит, то печатает )зе11о, игох1г1 Не обнаружив целых х, у и х, удовлетворяющих данному уравнению, она продолжает поиск до бесконечности и никогда не печатает)ге11о, ыох1с1.
Для того чтобы понять, как работает эта программа, сначала заметим, что ехр является встроенной функцией вычисления экспоненты. Основной программе нужно искать тройки (х, у, х) в порядке, гарантирующем, что каждая тройка в конце концов достигается. Для корректного поиска используется четвертая переменная, соса1, которая инициируется значением 3 и увеличивается в ччЫ1е-цикле каждый раз на 1, так что ее значение в конце концов достигает любого натурального числа. Внутри !ип1!е-цикла Сога1 разделяется на три положительных целых х, у и х, причем х изменяется в Гог-цикле от 1 до сосе1-2, у внутри этого )ог-цикла изменяется от 1 до соса1-х-1, а остаток значения соса1, между ! и соса1-2, становится значением х.
Во внутреннем цикле для тройки (х, у, х) проверяется равенство х" + у" =- г". Если оно выполняется, то печатается )те11о, ыох1с), а если нет — не печатается ничего. ' В. Ъг. Кегп)8)мп апд О. М. йнсше, Пге С Ргоягатт!пя 2апяиаяе, ! 978, Ргепг)се-На) 1, Епй!еиоос) СЫВ, КЬ (Керниган Б., Ритчи Д, Язык программирования Сн. — Ма Финансы и статистика, 1992. См.
также Керниган Б., Ритчи Д., Фьюэр А. Язык программирования Си. Задачи по языку Си. — Мя Финансы н сгатистика, 1985.) 320 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА Ьпс ехр(дпс 1, и) /* вычисление 1 в степени и */ ( Ьпс апя, апя = 1! Еог (3=1; 3<=п; 3++) апя *= гегпгп(апя); па1п () ( Ьпг и, соса1, х, у, ясапЕ("Ъс(", и); соса1 = 3; и)з11е (1) йог (х=1! х<=гога1-2! х++) аког (у=1! х<=сога1-х-1! у++)( Сога1 — х — у! (ехр(х,п) + ехр(у,п) == ехр (х и) ) рг1пСЕ(")зе11о, ыог1Ып")! ) сога1+е; Рис. 8.2 Вея икая теорема Ферма, выражеяпая в программе приветствия мира Если прочитано значение 2, то программа находит набор значений сога1 = 12, х = 3, у= 4 н г = 5, для которого х" + у" = г".
Таким образом, если на входе 2, то программа дейпнительно печатает )зе11о, ыог1о1 Однако для любого и > 2 программа никогда не найдет тройку положительных целых, ' удонлетворяюших х" +у" = е", и )зе11о, гяог1д напечатано не будет. Интересно, что вще несколько лет назад не было известно, печатает ли данная программа )зе11о, вог1с), т.е. имеет ли уравнение х" +у" = х" для некоторого большого и. Утверждение, что зю уравнение не имеет решений, было сформулировано Ферма более 300 лет назад, нодо недавних пор доказательство не было найдено. Данное утверждение часто называется "великой теоремой Ферма" ("гегпза('з!ам ((зеогеш*'). Определим проблему "/ге!!о, ног!с!" следующим образом.
По данной С-программе и ее входу определить, печатает ли она в качестве первых 12 символов )зе11о, ыог1с). В наньнейшем для краткости утверждение о юм, что программа печатает )зе11о, игог1с(, употребляется в смысле;что она печатает )зе11о, ьгог16 как первые 12 символов. Поскольку математикам понадобилось более 300 лет для решения вопроса, выраженного простенькой 22-строчной программой, то представляется правдоподобным, что об- $.1. ЗАДАЧИ, НЕ РЕШАЕМЫЕ КОМПЬЮТЕРАМИ 321 щая задача распознавания, печатает ли 1ге11о, гчот1с1 данная программа с данным входом, должна быть действительно сложной. Таким образом, любую задачу, не решенную математиками до сих пор, можно поставить как вопрос вида "печатает ли 1ге11о, ыот1с! данная программа с данным входом?". Было бы замечательно, если бы нам удалось написать программу, которая проверяет любую программу Р и ее вход! и определяет, печатается ли 1ге11о, гчог1с1 при выполнении Р со входом 1.
Мы докажем, что такой программы не может быть. Почему должны существовать неразрешимые проблемы Нелегко доказать, что какая-то определенная проблема, например, обсуждаемая здесь проблема "!ге!1о, вог1б", должна быть неразрешимой. Однако легко понять, почему почти все проблемы должны быть неразрешимыми в рамках любой системы, включающей программирование. Вспомним, что "проблема" — это в действительности вопрос о принадлежности цепочки языку. Множество различных языков над любым алфавитом, в котором более одного символа, несчетгю. Таким образом, невозможно г пронумеровать языки натуральными числами так, чтобы каждый язык получил номер, и каждое число было назначено одному языку.
С другой стороны, программы, будучи конечными цепочками в конечном алфавите (обычно зто подмножество алфавита АГАСИ), допускают такую нумерацию, т.е. образуют счетное множество. Их можно упорядочить по длине, а программы одной длины расположить в лексикографическом порядке. Таким образом, можно говорить о программе с номером 1, 2 и вообще с номером Л В результате можно утверждать, что проблем существует "бесконечно болыпе", чем программ.
Если случайно выбрать язык, то почти наверняка он окажется неразрешимой проблемой. И то, что проблемы в большинстве своем кажуигся разрешимыми, обусловлено лишь редкостью обращения к случайным проблемам. Наоборот, мы склонны к изучению относительно простых, хорошо структурированных проблем, и, действительно, они часто разрешимы. Однако лаже среди проблем, которые интересуют нас и допускают ясную и краткую формулировку, можно найти много неразрешимых, и в том числе проблему "!ге!! о, в"ог1г!".
8Л.2. Гипотетическая программа проверки приветствия мира Докажем невозможность создания программы проверки приветствия мира (печати "!геПо, зчог!г!") методом от противного. Предположим, что существует программа, скажем, Н, которая получает на вход программу Р и ее вход 1 и сообщает, печатает ли Р, имея на входе 7, текст !ге11о, ыаг1с1 Работа Н представлена на рис.
8.3. В частности, Н всегда печатает либо уев (да), либо по (нет), и ничего более. г Это справедливо н для односимвояьного алфавита. — Прим. ред. ГЛАВА 8. ВВедение В теОРию мАшин тьюРинГА 322 Если проблема имеет алгоритм, подобный программе Н, который на любом экземпляре проблемы правильно отвечает "да*' или "нет", то такая проблема называется "разрешимой". В противном случае проблема "неразрешима". Наша цель — доказать, что Н не существует, т.е.
проблема ")те11о, игог1сТ' является неразрешимой. уеи по Рис. 8.3. Гипотетическая программа обиаружеяия "'пейо, иог!й" Для доказательства этого утверждения методом от противного внесем в Н несколько юнеиений, построив в итоге программу Н„и докажем, что ее не существует. Поскольку шнеиения, вносимые в Н, можно совершить с любой С-программой, единственным сонвительным утверждением будет существование Н, т.е. утверждение, которое мы и опровергнем.
Для простоты доказательства сделаем несколько допущений о С-программах. Эти гипотезы упрощают, а не усложняют работу Н, поэтому, если доказать, что программы проверки ")те11о, игог1ср' не существует для таких ограниченных С-программ, то для более широкого класса программ такой программы проверки тем более не может быть. Итак, допустим следующее. 1, Весь выход программ состоит из символов, т.е. графические и иные средства несимвольного представления информации не используются. Все символы печатаются с помощью функции рт1псй, без использования росс)заг ( ) и других. Теперь предположим, что Н существует.
Наша первая модификация изменяет выход по, который является откликом Н, когда ее входная программа Р со своим входом У не печатает)зе11о, ыог1с). Как только Н печатает "п", нам становится понятно, что далее раяо или поздно появится "о".з Таким образом, каждый вызов рс1псб в Н изменим так, чтобы вместо "и" печаталось )зе11о, игог1д. Другие вызовы, которые печатают "о" без "и*', опускаются. В результате получим программу Нь которая ведет себя точно так ке, как и Н, но печатает )зе11о, чеог1д вместо по (рис. 8.4).
Следующее преобразование программы несколько сложнее. Оно, по сути, представляет собой прием, позволивший Алану Тьюрингу доказать свой результат о неразрешииости для машин Тьюринга. Поскольку нас в действительности интересуют программы, ' Наиболее вероятно, что программа печатает по в одном вызове ркьпес, но она мажЕт пЕчапть "и" водном вызове рг1пгс, а "о" — в следующем, 8.1, ЗАДАЧИ, НЕ РЕШАЕМЫЕ КОМПЬЮТЕРАМИ 323 которые получают на вход другие программы и что-то о них сообщают, ограничим Н, следующим образом.
уев Ьещо, иос1д Рис. 84 Н, ведет себя, как Н, но печатает Пе11о, иох1с! вместо по 1. Она получает на входтолько Р, а не Р и1. 2. Она отвечает, что сделала бы Р, если бы ее входом была она сама, т.е. что выдала бы Нь имея на входе Р в качестве как программы, так и входа У. Для создания программы Н,, представленной на рис. 8.5, внесем в Н! следующие изменения. 1. Вначале Нз считывает весь вход Р и запоминает его в массиве А, выделяя память под массив с помощью жа11ос'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
