dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 73

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 73)

Число состояний настолько велико, а пределы настолько размыты, что прийти к каким-либо полезнымзаключениям невозможно. В действительности, есть все причины поверить в то, чтопри желании множество состояний компьютера можно расширять до бесконечности.Например, целые числа можно представить в виде связанных списков цифр произвольной длины. Если память исчерпывается, программа печатает запрос на заменузаполненного диска новым, пустым.

И такие запросы могут повторяться по мере надобности сколько угодно раз. Такая программа будет намного сложнее, чем приведенная на рис. 8.2, но все равно мы сможем ее написать. Подобные приемы позволятлюбой другой программе обойти ограничения на размер памяти, величину целых чисел и другие параметры.Итак, имея программу Q и ее вход y, мы должны построить программу R и ее вход zтак, чтобы R со входом z вызывала foo тогда и только тогда, когда Q со входом y печатает hello, world. Конструкция проста.1.Если Q имеет вызываемую функцию foo, переименовать ее и все ее вызовы. Очевидно, новая программа Q1 выполняет то же самое, что и Q.2.Добавить в Q1 функцию foo.

Эта функция не делает ничего и не вызывается. Полученная программа называется Q2.3.Изменить Q2 так, чтобы первые 12 символов ее печати запоминались в глобальноммассиве A. Пусть полученная программа называется Q3.4.Изменить Q3 так, чтобы после каждого выполнения инструкции печати с использованием массива A проверялось, напечатано ли не менее 12 символов, и если так, тоне образуют ли первые 12 символов текст hello, world. В этом случае вызватьновую функцию foo, добавленную в п. 2. Полученная программа есть R, а ее вход zсовпадает с y.Предположим, что Q со входом y печатает hello, world в качестве начала своеговыхода.

Тогда построенная R вызывает foo. Однако если Q со входом y не печатает сначала hello, world, то R со входом z никогда не вызывает foo. Если можно решить,8.1. ÇÀÄÀ×È, ÍÅ ÐÅØÀÅÌÛÅ ÊÎÌÏÜÞÒÅÐÀÌÈСтр. 327327вызывает ли R со входом z функцию foo, то можно и решить, печатает ли Q со входом yсначала hello, world. Поскольку нам известно, что алгоритма решения проблемы“hello, world” нет, и все 4 этапа построения R по Q можно выполнить, отредактировав код, то предположение о том, что программа разрешения проблемы “calls-foo” существует, ложно. Такой программы нет, и данная проблема неразрешима. †Íàïðàâëåíèå ñâåäåíèÿ ÿâëÿåòñÿ âàæíûìОбычная ошибка — пытаться доказывать неразрешимость проблемы P2 путем сведения ее к известной неразрешимой проблеме P1, т.е. доказывать утверждение “если P1разрешима, то P2 разрешима”.

Это утверждение, безусловно, истинное, бесполезно,поскольку предпосылка “P1 разрешима” ложна.Единственный путь доказать, что новая проблема P2 неразрешима, состоит в том,чтобы свести к ней уже известную неразрешимую проблему, т.е. доказать утверждение “если P1 неразрешима, то P2 неразрешима”. Поскольку неразрешимость P1 ужеустановлена, приходим к выводу, что P2 неразрешима.8.1.4. Óïðàæíåíèÿ ê ðàçäåëó 8.18.1.1.Сведите проблему “hello, world” к каждой из следующих проблем. Используйте неформальный стиль данного раздела для описания правдоподобных преобразований программ и не беспокойтесь о реальных пределах размеров файлаили памяти в компьютерах:а) (!∗) по данной программе и ее входу определить, останавливается ли она когда-нибудь, т.е.

не зацикливается ли при данном входе;б) по данной программе и ее входу определить, печатает ли она вообще чтонибудь;в) (!) по данным двум программам и входу определить, порождают ли они одини тот же выход при данном входе.8.2. Ìàøèíà ÒüþðèíãàЦель теории неразрешимых проблем состоит не только в том, чтобы установить существование таких проблем (что само по себе не просто), но также в том, чтобы обеспечить программистов информацией, какие задачи программирования можно решить, а какие нельзя. Теория также имеет огромное практическое значение, когда рассматриваются проблемы, которые хотя и разрешимы, но требуют слишком большого времени для ихрешения (см.

главу 10). Эти проблемы, называемые “трудно разрешимыми”, или“труднорешаемыми”, подчас доставляют программистам и разработчикам систем больше хлопот, чем неразрешимые проблемы. Причина в том, что неразрешимые проблемы328Стр. 328ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀредко возникают на практике, тогда как трудно разрешимые встречаются каждый день.Кроме того, они часто допускают небольшие модификации условий или эвристическиерешения.

Таким образом, разработчику постоянно приходится решать, относится лиданная проблема к классу труднорешаемых и что с ней делать, если это так.Нам нужен инструмент, позволяющий доказывать неразрешимость или труднорешаемость повседневных вопросов. Методика, представленная в разделе 8.1, полезна длявопросов, касающихся программ, но ее нелегко перенести на проблемы, не связанные спрограммами. Например, было бы нелегко свести проблему “hello, world” к проблеме неоднозначности грамматики.Таким образом, нужно перестроить нашу теорию неразрешимости, основанную не напрограммах в языке С или других языках, а на очень простой модели компьютера, котораяназывается машиной Тьюринга. Это устройство по существу представляет собой конечныйавтомат с бесконечной лентой, на которой он может как читать, так и записывать данные.Одно из преимуществ машин Тьюринга по сравнению с программами как представлениемвычислений состоит в том, что машина Тьюринга достаточно проста и ее конфигурациюможно точно описать, используя нотацию, весьма похожую на МО МП-автоматов.

Длясравнения, состояние С-программы включает все переменные, возникающие при выполнении любой цепочки вызовов функций, и нотация для описания этих состояний настолькосложна, что практически не позволяет проводить понятные формальные доказательства.С использованием нотации машин Тьюринга будет доказана неразрешимость некоторых проблем, не связанных с программированием.

Например, в разделе 9.4 будет показано, что “проблема соответствий Поста”, простой вопрос о двух списках цепочек, неразрешим, и что эта проблема облегчает доказательство неразрешимости вопросов ограмматиках, вроде неоднозначности. Аналогично, когда будут введены трудно разрешимые проблемы, мы увидим, что к их числу принадлежат и определенные вопросы, казалось бы, не связанные с вычислениями, например, выполнимость булевских формул.8.2.1. Ïîèñêè ðåøåíèÿ âñåõ ìàòåìàòè÷åñêèõ âîïðîñîâВ начале XX столетия великий математик Д.

Гильберт поставил вопрос о поисках алгоритма, который позволял бы определить истинность или ложность любого математического утверждения. В частности, он спрашивал, есть ли способ определить, истиннаили ложна произвольная формула в исчислении предикатов первого порядка с целымичислами.

Исчисление предикатов первого порядка с целыми (арифметика) достаточномощно, чтобы выразить утверждения типа “эта грамматика неоднозначна” или “эта программа печатает hello, world”. Поэтому, окажись предположение Гильберта правильным, данные проблемы были бы разрешимыми.Однако в 1931 г. К. Гедель опубликовал свою знаменитую теорему о неполноте. Ондоказал, что существует истинная формула первого порядка с целыми, которую нельзяни доказать, ни опровергнуть в исчислении предикатов первого порядка над целыми. Его8.2.

ÌÀØÈÍÀ ÒÜÞÐÈÍÃÀСтр. 329329техника доказательства похожа на конструкцию противоречивой программы H2 из раздела 8.1.2, но имеет дело с функциями целого аргумента, а не с С-программами.Исчисление предикатов было не единственным понятием, применяемым для формализации “любого возможного вычисления”. В действительности, исчисление предикатов,будучи декларативным, а не вычислительным, конкурировало с различными нотациями,включая “частично рекурсивные функции”. В 1936 г.

А. М. Тьюринг в качестве модели“любого возможного вычисления” предложил машину Тьюринга. Эта модель была недекларативной, а “машиноподобной”, хотя настоящие электронные и даже электромеханические машины появились лишь несколько лет спустя (и сам Тьюринг занимался ихразработкой во время второй мировой войны).Интересно, что все когда-либо предложенные серьезные вычислительные моделиимеют одинаковую мощность, т.е. все они вычисляют одни и те же функции или распознают одни и те же множества. Недоказуемое предположение, что любой общий методвычислений позволяет вычислять лишь частично рекурсивные функции (и их же способны вычислять машины Тьюринга или современные компьютеры), известно как гипотезаЧерча (следуя логике А.

Черча), или тезис Черча-Тьюринга.8.2.2. Îïèñàíèå ìàøèí ÒüþðèíãàМашина Тьюринга изображена на рис. 8.8. Машина состоит из конечного управления,которое может находиться в любом из конечного множества состояний. Есть лента, разбитая на клетки; каждая клетка может хранить любой символ из конечного их множества.КонечноеуправлениеРис. 8.8. Машина ТьюринтаИзначально на ленте записан вход, представляющий собой цепочку символов конечной длины.

Символы выбраны из входного алфавита. Все остальные клетки, до бесконечности, слева и справа от входа содержат специальный символ, называемый пустымсимволом, или пробелом. Он является не входным, а ленточным символом. Кроме входных символов и пробела возможны другие ленточные символы.Ленточная головка (далее просто головка) всегда устанавливается на какую-то изклеток ленты, которая называется сканируемой, или обозреваемой. Вначале обозреваетсякрайняя слева клетка входа.330Стр. 330ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀПереход машины Тьюринга — это функция, зависящая от состояния конечногоуправления и обозреваемого символа.

За один переход машина Тьюринга должна выполнить следующие действия.1.Изменить состояние. Следующее состояние может совпадать с текущим.2.Записать ленточный символ в обозреваемую клетку. Этот символ замещает любойсимвол в этой клетке, в частности, символы могут совпадать.3.Сдвинуть головку влево или вправо. В нашей формализации не допускается, чтобы головка оставалась на месте.

Характеристики

Список файлов книги