Тени разума. В поисках науки о сознании - страница 52

не завершается вычисление (G), вполне очевиден. Какими же процедурами располагают математики для установления незавершаемой природы таких вычислений в общем случае? Можно ли сами эти процедуры представить в вычислительной форме?

Предположим, что у нас имеется некая вычислительная процедура А, которая по завершении[9] дает нам исчерпывающее доказательство того, что вычисление C(n) действительно никогда не заканчивается. Ниже мы попробуем вообразить, что A включает в себя все известные математикам процедуры, посредством которых можно убедительно доказать, что то или иное вычисление никогда не завершается. Соответственно, если в каком-то конкретном случае завершается процедура A, то мы получаем, в рамках доступного человеку знания, доказательство того, что рассматриваемое конкретное вычисление никогда не заканчивается. Большая часть последующих рассуждений не потребует участия процедуры A именно в такой роли, так как они посвящены, в основном, математическим умопостроениям. Однако для получения окончательного заключения G нам придется-таки придать процедуре A соответствующий статус.

Я, разумеется, не требую, чтобы посредством процедуры A всегда можно было однозначно установить, что вычисление C(n) нельзя завершить (в случае, если это действительно так); однако я настаиваю на том, что неверных ответов A не дает, т.е. если мы с ее помощью пришли к выводу, что вычисление C(n) не завершается, значит, так оно и есть. Процедуру A, которая и в самом деле всегда дает верный ответ, мы будем называть обоснованной.

Следует отметить, что если процедура A оказывается в действительности необоснованной, то этот факт, в принципе, можно установить с помощью прямого вычисления — иными словами, необоснованную процедуру A можно опровергнуть вычислительными методами: если А ошибочно утверждает, что вычисление C(n) нельзя завершить, тогда как в действительности это не так, то выполнение самого вычисления C(n) в конечном счете приведет к опровержению А. (Возможность практического выполнения такого вычисления представляет собой отдельный вопрос, его мы рассмотрим в ответе на возражение Q8.)

Для того чтобы процедуру A можно было применять к вычислениям в общем случае, нам потребуется какой-нибудь способ маркировки различных вычислений C(n), допускаемый A. Все возможные вычисления C можно, вообще говоря, представить в виде простой последовательности

т.е. q-e вычисление при этом получит обозначение C_>q. В случае применения такого вычисления к конкретному числу n будем записывать

Можно представить, что эта последовательность задается, скажем, как некий пронумерованный ряд компьютерных программ. (Для большей ясности мы могли бы, при желании, рассматривать такую последовательность как ряд пронумерованных машин Тьюринга, описанных в НРК; в этом случае вычисление C_>q(n) представляет собой процедуру, выполняемую q-й машиной Тьюринга T_>q над числом n.) Здесь важно учитывать следующий технический момент: рассматриваемая последовательность является вычислимой — иными словами, существует одно-единственное[10] вычисление C_>•, которое, будучи выполнено над числом q, дает в результате C_>q, или, если точнее, выполнение вычисления C_>• над парой чисел q, n (именно в таком порядке) дает в результате C_>q(n).

Можно полагать, что процедура A представляет собой некое особое вычисление, выполняя которое над парой чисел q, n, можно однозначно установить, что вычисление C_>q(n), в конечном итоге, никогда не завершится. Таким образом, когда завершается вычисление A, мы имеем достаточное доказательство того, что вычисление C_>q(n) завершить невозможно. Хотя, как уже говорилось, мы и попытаемся вскоре представить себе такую процедуру A, которая формализует все известные современной математике процедуры, способные достоверно установить невозможность завершения вычисления, нет никакой необходимости придавать A такой смысл прямо сейчас. Пока же процедурой A мы будем называть любой обоснованный набор вычислительных правил, с помощью которого можно установить, что то или иное вычисление