Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

Допустим, что проблема, решаемая на машине Тьюринга 3J?, состоит в вычислении значений некоторой числовой функ­ ции ф (п) при /1=1, 2, 3,... Мы уже знаем (см. п. 11.3), что такая функция может оказаться очень быстро растущей. Вспомним, например, функцию ср, принимающую для аргу­ мента п значение З 2 ' (п этажей!), хотя, конечно, и такой внушительный рост может быть превзойден. Если значения аргумента и самой функции записываются унарно, то для любой машины Ш, вычисляющей ф, Тэд (п) будет не меньше, чем ф (/г); ведь машине потребуется такое коли­ чество тактов уже только для того, чтобы записать резуль­ тат— ф (п) палочек. В этом смысле, вычисляя быстро рас­ тущие функции, мы уже столкнулись со сколь угодно слож­ ными проблемами. Это положение сохранилось бы и в том случае, когда числа записываются в какой-нибудь позицион­

добных ситуациях много времени тратится машиной на за­

не громоздок (результирующее слово короткое), а значит почти все время тратится машиной на вычисление резуль­ тата. В связи с этим ограничимся рассмотрением лишь проб­ лем, заключающихся в распознавании свойства исходных данных; в этой ситуации решение может быть дано в виде однобуквенного слова «1» (да) или «0» (нет). (Пользуясь терминологией, употребляемой в логике, можно сказать, что это есть проблема вычисления предиката.) Среди таких проблем, как мы уже знаем, имеются и алгоритмически неразрешимые (например, распознавание самоприменимо­ сти, распознавание эквивалентности слов и др.). Если же проблема распознавания алгоритмически разрешима, то

157

время, затрачиваемое на решение тех или иных индивидуаль­ ных ее задач при использовании конкретного алгоритма (например, тыорпнговой программы Ж), уходит почти це­

Тьюринга 31, которая распознает то же самое свойство, и при этом

/fSR(P)<f(P) для всех слов Р.

Существование такой вычислимой функции — пусть и очень быстро растущей — мы могли бы расценивать как свиде­ тельство того, что алгоритмически разрешимые проблемы не бывают сколь угодно сложными, ибо всегда можно обойтись алгоритмами с заранее ограниченным числом шагов при обработке слова длиной п. Более того, в качестве приемлемой верхней границы мы располагали бы вычислимой функцией/.

20.2. Распознавание /-самоприменимости. На самом же деле оказывается, что такой вычислимой функции не суще­

(ЩР) > f (Р) для бесчисленного множества слов Р.

Доказательство этой теоремы получается путем подходя­ щей (и поучительной!) модификации теоремы п. 15.2 об алго­ ритмической неразрешимости проблемы распознавания самопрнменимости. Пусть / (Р) — вычисляемая функция из условий теоремы. Тогда, если на ленте произвольной ма­ шины 93? записан ее собственный шифр €0?' и машина запущена в работу, то возможен один и только один из следующих трех случаев: 1) машина 3)? не остановится в течение пер-

158

вых / (93?") тактов; 2) машина 93? остановится не позже чем через [ (50?') тактов и выдаст результат 1; 3) машина 2)? остановится не позже чем через / (S3?') тактов и выдаст ре­ зультат, отличный от 1.

Условимся говорить о машине Ж, что она /-самопримени­ ма, если имеет место ситуация 3) и что она /-несамопримени­ ма в противном случае, т. е. в ситуациях 1) и 2). Естествен­ но, возникает проблема распознавания/-самоприменимости: для любого двоичного слова Р узнать, является ли оно шиф­ ром /-самопримеиимой машины (короче, является ли Р /-самоприменимым шифром). При всем внешнем сходстве с проблемой самоприменимости имеет место, однако, сле­ дующий факт; проблема распознавания /-самопримени­ мости алгоритмически разрешима. Разрешающий алгоритм 2( заключается в следующем. 1. Для данного слова Р про­

в п. 14.2. Если Р не является шифром, то тем более оно не является /-самоприменимым шифром и ответ (отрицатель­ ный) уже найден. 2. Если Р является шифром, то сначала вычисляем число / (Р). Это можно сделать эффективно, ибо по предположению функция / (Р) вычислима, т. е. суще­ ствует алгоритм (машина Тьюринга), который по каждому слову Р позволяет находить значение / (Р). 3. Далее, по шифру Р восстанавливаем схему машины и, запуская ее в начальной конфигурации с записью слова Р, следим за ее работой в течение не более чем / (Р) тактов. Это позволяет нам фактически установить, какая из ситуаций (1, 2, 3) имеет место и, следовательно, позволяет получить правиль­ ный ответ на вопрос: /-самоприменим ли шифр Р?

Итак, нужный алгоритм описан. В отличие от общей проблемы распознавания самоприменимости, в которой машина может работать неограниченно долго, здесь ока­

тактов ее работы. Пусть $ — какая-нибудь машина Тьюрин­

если 93?' /-самоприменима; (**) $ перерабатывает 93?' в 0, если 93?' / несамоприменима. По аналогии с доказательством из § 15 посмотрим, как будет перерабатывать машина $ свой собственный шифр

159

1) пусть S f-самоприменима; тогда по определению f-самоприменимости (вариант 3) она выдает результат, от­ личный от 1. Но согласно (**) это означает, что на самом деле й выдает результат 0, а следовательно, ®/-несамо- применима. Полученное противоречие заставляет нас (так же, как и в п. 15.2) отвергнуть предположение о /-самопри­ менимости машины ®;

2) пусть й /-несамоприменима; тогда по определению возможен один из вариантов (1 или 2). Вариант 2 приводит к противоречию в точности так же, как это было обнару­ жено для варианта 1. Тем самым выясняется, что имеется лишь одна возможность, а именно, что реализуется вариант 1, т. е. справедливо утверждение: если машина Й распознает

Р в стандартной конфигурации, то они будут работать со­

они также распознают /-самоприменимость, а следовательно,

можно при условиях теоремы обнаружить существование такого свойства Г двоичных слов, для которого утвержде­ ние б) теоремы справедливо в следующей более сильной форме (теорема Рабииа): б) Какова бы ни была машина £, распознающая это свойство Г, ее временная сигнализирую­ щая (й удовлетворяет неравенству t% (Р) > / (Р) для всех двоичных слов Р за исключением конечного их числа.

160