dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 72
Текст из файла (страница 72)
Если случайно выбрать язык, то почти наверняка он окажется неразрешимой проблемой. И то, что проблемы в большинстве своем кажутся разрешимыми,обусловлено лишь редкостью обращения к случайным проблемам. Наоборот, мысклонны к изучению относительно простых, хорошо структурированных проблем, и,действительно, они часто разрешимы. Однако даже среди проблем, которые интересуют нас и допускают ясную и краткую формулировку, можно найти много неразрешимых, и в том числе проблему “hello, world”.8.1.2. Ãèïîòåòè÷åñêàÿ ïðîãðàììà ïðîâåðêè ïðèâåòñòâèÿ ìèðàДокажем невозможность создания программы проверки приветствия мира (печати“hello, world”) методом от противного.
Предположим, что существует программа, скажем, H, которая получает на вход программу P и ее вход I и сообщает, печатает ли P,2322Стр. 322Это справедливо и для односимвольного алфавита. — Прим. ред.ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀимея на входе I, текст hello, world. Работа H представлена на рис. 8.3. В частности,H всегда печатает либо yes (да), либо no (нет), и ничего более.Если проблема имеет алгоритм, подобный программе H, который на любом экземпляре проблемы правильно отвечает “да” или “нет”, то такая проблема называется“разрешимой”. В противном случае проблема “неразрешима”. Наша цель — доказать,что H не существует, т.е. проблема “hello, world” является неразрешимой.Программаобнаружения"hello, world"Рис. 8.3. Гипотетическая программа обнаружения “hello, world”Для доказательства этого утверждения методом от противного внесем в H несколькоизменений, построив в итоге программу H2, и докажем, что ее не существует.
Посколькуизменения, вносимые в H, можно совершить с любой С-программой, единственным сомнительным утверждением будет существование H, т.е. утверждение, которое мы и опровергнем.Для простоты доказательства сделаем несколько допущений о С-программах. Эти гипотезы упрощают, а не усложняют работу H, поэтому, если доказать, что программыпроверки “hello, world” не существует для таких ограниченных С-программ, то дляболее широкого класса программ такой программы проверки тем более не может быть.Итак, допустим следующее.1.Весь выход программ состоит из символов, т.е. графические и иные средства несимвольного представления информации не используются.2.Все символы печатаются с помощью функции printf, без использованияputchar() и других.Теперь предположим, что H существует.
Наша первая модификация изменяет выходno, который является откликом H, когда ее входная программа P со своим входом I непечатает hello, world. Как только H печатает “n”, нам становится понятно, что далеерано или поздно появится “o”.3 Таким образом, каждый вызов printf в H изменим так,чтобы вместо “n” печаталось hello, world. Другие вызовы, которые печатают “o”без “n”, опускаются. В результате получим программу H1, которая ведет себя точно также, как и H, но печатает hello, world вместо no (рис. 8.4).3Наиболее вероятно, что программа печатает no в одном вызове printf, но она может печатать “n” в одном вызове printf, а “o” — в следующем.8.1. ÇÀÄÀ×È, ÍÅ ÐÅØÀÅÌÛÅ ÊÎÌÏÜÞÒÅÐÀÌÈСтр. 323323Следующее преобразование программы несколько сложнее. Оно, по сути, представляет собой прием, позволивший Алану Тьюрингу доказать свой результат о неразрешимости для машин Тьюринга.
Поскольку нас в действительности интересуют программы,которые получают на вход другие программы и что-то о них сообщают, ограничим H1следующим образом.Рис. 8.4. H1 ведет себя, как H, но печатает hello, world вместо no1.Она получает на вход только P, а не P и I.2.Она отвечает, что сделала бы P, если бы ее входом была она сама, т.е. что выдала быH1, имея на входе P в качестве как программы, так и входа I.Для создания программы H2, представленной на рис. 8.5, внесем в H1 следующиеизменения.1.Вначале H2 считывает весь вход P и запоминает его в массиве A, выделяя память подмассив с помощью malloc4.2.Затем H2 имитирует H1, но вместо чтения из P или I программа H2 читает из копии вмассиве A.
Для запоминания мест в P и I, до которых дочитала H1, H2 может содержать два курсора, отмечающих позиции в A.Рис. 8.5. H2 ведет себя, как H1, но использует вход P в качестве как P, так и IТеперь все готово для доказательства того, что H2 не существует. Таким образом, несуществует H1 и, аналогично, H. Для того чтобы в этом убедиться, нужно представитьсебе, что делает H2, когда получает себя в качестве входа (рис. 8.6). Напомним, что H2,4Функция malloc системы UNIX распределяет блок памяти, размер которого задается в ее вызове.Эта функция используется, когда нужный размер памяти невозможно определить до начала выполненияпрограммы, как и при чтении входа произвольной длины.
Обычно malloc вызывается несколько раз помере того, как возрастают объем прочитанного входа и потребность в памяти.324Стр. 324ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀполучив некоторую программу P на вход, печатает yes, если P печатает hello,world, получая себя в качестве входа.
Кроме того, H2 печатает hello, world, если P,получив себя на вход, не выдает hello, world в качестве начала своего выхода.Рис. 8.6. Что делает H2, получая себя в качестве входа?Предположим, что H2 в рамке (см. рис. 8.6) печатает yes. Тогда H2 в рамке говорит о своем входе H2, что H2, получая себя в качестве входа, выдает вначале hello, world. Но мытолько что предположили, что выход H2 начинается текстом yes, а не hello, world.Таким образом, получается, что выходом программы в рамке (см. рис. 8.6) являетсяне yes, а hello, world, поскольку возможно либо одно, либо другое. Но если H2, получая себя на вход, печатает hello, world, то выходом программы в рамке нарис. 8.6 должно быть yes.
Каким бы ни был предполагаемый выход H2, доказано, чтоона печатает противоположное.Описанная ситуация противоречива, и мы приходим к выводу, что H2 не может существовать. Это опровергает предположение о существовании H. Таким образом, доказано,что ни одна программа H не может сказать, печатает ли данная программа P со входом Iтекст hello, world.8.1.3. Ñâåäåíèå îäíîé ïðîáëåìû ê äðóãîéПечатает ли данная программа в начале своего выхода текст hello, world? Мыуже знаем, что ни одна компьютерная программа этот вопрос разрешить не может. Проблема, которую нельзя разрешить с помощью компьютера, называется неразрешимой.Формальное определение “неразрешимого” будет дано в разделе 9.3, а пока этот терминиспользуется неформально.
Предположим, что нам нужно определить, разрешима ли некоторая новая проблема. Мы можем попытаться написать программу для ее разрешения,но, если нам непонятно, как это сделать, мы можем попробовать доказать, что такойпрограммы не существует.Неразрешимость новой проблемы можно было бы доказать аналогично тому, как этобыло сделано для проблемы “hello, world”: предположить, что программа разрешениясуществует, и построить противоречивую программу, которая должна делать одновременно две взаимно исключающие вещи, как программа H2. Однако если у нас есть проблема, неразрешимость которой установлена, то нам не обязательно вновь доказыватьпротиворечивость. Достаточно показать, что если новая проблема имеет решение, то его8.1.
ÇÀÄÀ×È, ÍÅ ÐÅØÀÅÌÛÅ ÊÎÌÏÜÞÒÅÐÀÌÈСтр. 325325можно использовать для разрешения уже известной неразрешимой проблемы. Такойподход представлен на рис. 8.7 и называется сведением P1 к P2.Предположим, нам известно, что проблема P1 неразрешима, а P2 — новая проблема,неразрешимость которой нужно доказать. Допустим, что существует программа, котораяпредставлена ромбом с отметкой “разрешить” (см. рис. 8.7) и печатает yes или no в зависимости от того, принадлежит или нет ее входной экземпляр проблемы P2 языку этойпроблемы.5ЭкземплярПостроитьЭкземплярРазрешитьРис. 8.7. Если бы можно было разрешить проблему P2, то ее решение мы моглибы использовать для разрешения проблемы P1Для доказательства неразрешимости проблемы P2 нужно создать алгоритм, которыйпредставлен квадратом на рис.
8.7 и преобразует любой экземпляр P1 в экземпляр P2,причем их ответы всегда совпадают. Имея такое преобразование, проблему P1 можноразрешить следующим образом.1.Применить алгоритм построения к данному экземпляру проблемы P1, т.е. к строке w,которая может принадлежать или не принадлежать языку P1, и получить строку x.2.Проверить, принадлежит ли x языку P2, и перенести ответ на w и P1.Пример 8.1. Применим описанный метод для доказательства, что вопрос “вызываетли когда-нибудь программа Q с данным входом y функцию foo” неразрешим.
Заметим,что в Q может не быть функции foo, и в этом случае задача решается просто. Однакоона становится сложной, если Q имеет функцию foo, но с y на входе может как достичь,так и не достичь вызова foo. Поскольку нам известна только одна неразрешимая проблема, роль P1 на рис. 8.7 играет проблема “hello, world”. В качестве P2 выступает описанная только что проблема “calls-foo”. Предположим, что существует программа разрешения этой проблемы. Наша задача — построить алгоритм, который преобразует проблему “hello, world” в проблему “calls-foo”.5Напомним, что проблема в действительности представляет собой язык. Говоря о проблемеразрешения, приводят ли данные программа и вход к печати hello, world, мы в действительности говорим о цепочках, образованных С-программами и их входными данными.
Это множествоцепочек является языком над алфавитом из символов ASCII.326Стр. 326ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄåéñòâèòåëüíî ëè êîìïüþòåð ìîæåò äåëàòü âñå ýòî?Если присмотреться к программе, представленной на рис. 8.2, можно спросить, действительно ли она находит контрпримеры к великой теореме Ферма. Как-никак, целые числа в типичном компьютере имеют всего 32 бит, и если самый маленькийконтрпример содержит числа, измеряемые биллионами, то произойдет ошибка переполнения, прежде чем отыщется решение. И вообще, компьютер со 128 Мбайт оперативной памяти и 30-гигабайтным диском имеет “всего” 25630128000000 состояний и является, таким образом, конечным автоматом.Однако рассмотрение компьютера как конечного автомата (или мозга как конечногоавтомата, откуда, кстати, происходит идея КА) непродуктивно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
