Теория синтаксического анализа, перевода и компиляции - Том 1 (Теория синтаксического анализа, перевода и компиляции), страница 9

То же самое можно сформулировать по-другому. Существуют отображения, которые нельзя задать никакими частичными алгоритмами, а также такие отображения, которые можно задать частичными алгоритмами, но нельзя всюду определенными. Мы увидим далее, что эти понятия имеют фундаментальное значение для теории программирования. В равд. 0.4.5 будет приведен прямер частичного алгоритма, для которого, как можно показать, не существует эквивалентного (всюду определенного) алгоритма.

0.4.4. Задание алгоритмов В предыдущем разделе было неформально определено, что мы понимаем под алгоритмом, частичным или всюду определенным. Можно дать строгие определения этих терл)ннов, используя разные формализмы. Существует много формальных способов описания алгоритмов. Отметим следующие: (1) Машины Тьюринга [Тьюринг, 1936 — 1937'1. (2) Грамматики Хамского типа 0 [Хомский, 1959а, 1963). (3) Алгоритмы Маркова [Марков, 19511. (4) Лямбда-исчисление [Черч, 1941). (5) Системы Поста [Пост, 1943).

(6) ТАГ-системы [Пост, 19651. (?) Большинство языков программирования [Саммет, 19691. родолжить. Здесь важно отметить, что ЭТОТ списОк можно пгодо о итм, записанный в одном из этих формализмов, можно прм записанным в любом другом из этих о мализмов, В этом смысле все перечисленные формализмы же экви ивалеитны. Че ч и Тьюринг выдвинули гипотезу, что Много лет назад ерч и ь о аз мно назвать любой вычислительный процесс, который можно разумн алго итмом, можно прои моделировать на машине Тьюринга. Эта ак тезис Чгрча — Тьюринга и является о щоб егииотсза известна как т бравом, наиболее общий класс множе ств п инятой.

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

В гл. 11 (том > мы увид 2) им, к чему приводит эта их спосоонос когда мы пытаемся Оптимизировать программы. "4 не б дем здесь обсуждать детали формализмов, предпатя некото ые из них знач енных для описания алгоритмов, хот в ение в эту область ' Р появятся в упражнениях. Очень доступное в ед со е жится в книге Минского [19671'). В нашей книге, как мы уже же видели для описания алгоритмов используется неформальная запись. 0„4д. Проблемы Слово проблема мы будем употреблять довольно специфическим образом. Определение. Проблема (или вопрос) — зто утверждение (предикат), истинное или ложное в зависимости от значений вхонего неизвестных (переменных) определенного типа.

дящих в него м гово им, что П блема обычно формулируется как вопрос, и мы р ответ на вопрос — „да", если это утверждение истинно, н „нет" если утверждение ложно. Пример 0.18. Примером проблемы служит следующее утверждение: „Целое число х меныпе целого числа 1>". Это утверждение можно выразить в более разговорном виде, устранив упо. минание о типе переменных х и и и придав ему форму вопросао йх меньше ПТ' () Определение. Чпгтный случай проблемы — это набор допустимых значений ее неизвестных.

Например, частными случаями проблемы примера 0.18 являются упорядоченные пары целых чисел. 1) можно порекомендовать также кккгу мальцева 119651.— прим, перев. 43 ГЛ. О. ПРВДВАРИТВЛЬНЫа »4АТИМАТИс!ЕСХИЕ СВЬДР ИИЯ Отображение множества частных случаев проблемы во множество (да, нет) называется решением проблемы. Если это отображение можно задать алгоритмом, то проблема называется (алгоритмически) разрешимой. Если алгоритма, определяющего это отображение, нет, то проблема называется (алгоритмически) неразрешимой. Одним из выдающихся достижений математики ХХ века было открытие алгоритмическн неразрешимых проблем. Позднее мы увидим, что неразрешимые проблемы серьезно затрудняют развитие широко применимой теории вычислений. Пример 0.19. Исследуем проблему: „Является лн частичный алгоритм Р (всюду определенным) алгоритмом?" Анализ этой проблемы покажет, почему некоторые проблемы оказываются неразрешимыми.

Сначала предположим, что все частичные алгоритмы описываются в некоторой формальной системе вроде тех, что были упомянуты ранее в этом разделе. В любом формальном языке, предназначенном для задания алгоритмов, можно, оказывается, описать только счетное число алгоритмов. Хотя мы не можем доказать это здесь в общем виде, рассмотрим один пример формализма — язык „абсолютиыхо машинных программ, а другие упомянутые формализмы отложим до упражнений. Любая программа в абсолютном машинном языке представляет собой конечную последовательность нулей и единиц (которые можно представлять себе сгруппированными в машинные слова по 32, Зб, 48 или другому числу знаков).

Допустим„у нас есть цепочка из нулей и единиц, представляющая программу в машинном языке. Зтой программе можно приписать натуральное число (номер), соответствующее ее положению в некотором полном упорядочении всех цепочек из нулей и единиц. Одно такое упорядочение можно получить, расположив цепочки по возрастанию их длин, а цепочки равной длины упорядочив лексикографически (при этом каждая цепочка рассматривается как двоичное число).

Так как число цепочек любой заданной длины конечно, то любой цепочке из множества (О, 1) * будет поставлено в соответствие некоторое целое положительное число. Первые несколько пар этого биективного соответствия приведены в табл. О.1. Таким образом, мы видим, что для каждой программы в машинном языке можно однозначно найти соответствующее целое положительное число и для каждого такого числа можно найти некоторую программу. Какой именно формализм выбирается для описания частичных алгоритмов, не имеет значения: всегда можно установить взаимно однозначное соответствие между частичнымн алгоритмами и целыми положительными числами. Таким образом, имеет смысл говорить об !'-м частичном алгоритме в любом данном ааи АЛГОРИТМЫ 1ЧАСТИЧ ИЫВ И ВСЮДУ ОПРВДРЛЕ У!ИЫВ алгоритмическом формализме.

Более того, это соответствие между алго горитмами и числами достаточно просто, так что по данному числу ! можно записать соответствующий алгоритм, а по данному алгоритму найти соответствующее число. Предположим, что существует частичный алгоритм Р,, который является (всюду определенным) алгоритмом, на его вход Таблица Од Число Цепочка е 0 ! 00 о! !о !! 000 00! подаются описания частичных алгоритмов в нашем формализме н он выдает ответ,дао для данного входа тогда и только тогда, !Тогда этот вход описывает (всюду определенный) алгоритм. Все известные формализмы, используемые для описания частичных алгоритмов, обладают тем свойством, что можно простыми способами комбинировать алгоритмы, получая таким образом новые алгоритмы.

В частности, если даи гипотетический алгоритм РР то можно построить алгоритм Р», который работает следующим образом: Алгоритм Р,. Вход. Любой частичный алгоритм Р, имеющий одну входную переменную. Выход. (1) еНет", если (а) Р не является алгоритмом или (6) Р является алгоритмом и Р (Р) =,дз", '(2) „Да" в остальных случаях. Запись Р(Р) означает, что мы применяем частичный алгоРитм Р к описанию его самого Метод. (1) Если Р,(Р) =„да", то перейти к шагу (2); в противном случае выдать на выходе „нет" и остановиться. (2) Если Р— алгоритм и его входы — описания частичных алгоритмов, в выходы †отве ,да" и „нет", то алгорит51 Р» пРименяет алгоритм Р к самому себе, т.

е. к своему описанию. 45 ГЛ. В ПРЕДВЛРИТЕЛЬ НЫЕ МАТЕМАТИЧЕСКИЕ СВ ЕДЕ НИЯ (При этом предполагается, что по описанию частичного алгоритма можно установить, имеют ли его входы и выходы указанный вид. Для известных формализмов это предположение верно.) (3) Рь выдает „нет" или,да", если Р выдает „да" или кисти соответственно. Г3 Ьфы видим, что Є— (всюду определенный) алгоритм, если Р— алгоритм. При этом Р„ имеет одну входную переменную. о что же делает Р„, когда он сам подается на свой входу По предположению алгоритм Р, определяет, что Р„ †алгори (т. е.

Р~(Рь) =-„да"), затем Р„ моделирует себя на себе, т. е. свое поведение на своем описании, взятом в качестве входа. Но тогда Р„не может дать непротиворечивый результат. Если Р„устанавливает, что моделирование дает результат „да", то Рь дает на выходе результат „иет". Но алгоритм Р„определен так, что в применении к самому себе он должен давать ответ,да". Аналогичный парадокс возникает, если Рь обнаруживает„что моделирование дает результат „нет".

Отсюда мы должны заключить, что предположение о существовании алгоритма Р, ошибочно, и, следовательно, проблема „является ли Р алгоритмому" неразрешима для любого известного алгоритмического формализма. Е;) Следует подчеркнуть, что проблема разрешима тогда и только тогда, когда существует алгоритм, который для любого частного случая этой проблемы дает ответ „да" или инет". Для конкретных частных случаев проблемь! иногда можно получить ответ „да" или „нет".

Но это еще не делает проблему разрешимой. Для того чтобы можно было говорить о разрешимости проблемы, нужно дать единый алгоритм, работающий для всех частных случаев проблемы. Следует особо отметить, что очень важную роль играет кодирование частных случаев проблемы. Обычно подразумевается некоторое „стандартное" кодирование (кодирование, для которого существует алгоритм, отображающий коды описаний алгоритмов в эквивалентные программы ма!пни Тьюринга). Если используются нестандартные кодирования, то неразрешимые проблемы могут стать разрешимыми.