Тени разума. В поисках науки о сознании
Шрифт:
2.5. Семейства вычислений; следствие Гёделя—Тьюринга G
Для того, чтобы понять, каким образом из теоремы Гёделя (в моей упрощенной формулировке, навеянной отчасти идеями Тьюринга) следует все вышесказанное, нам необходимо будет сделать небольшое обобщение для типов утверждений, относящихся к рассмотренным в предыдущем разделе вычислениям. Вместо того чтобы решать проблему завершаемости для каждого отдельного вычисления ( (A), (B), (C), (D)или (E)), нам следует рассмотреть некоторое общее вычисление, которое зависит от натурального числа n(либо как-то воздействуетна него). Таким образом, обозначив такое вычисление через C( n), мы можем рассматривать его как целое семействовычислений, где для каждого натурального числа (0, 1, 2, 3, 4, …) выполняется отдельное вычисление (соответственно, C(0), C(1), C(2), C(3), C(4), …),
В терминах машин Тьюринга это всего лишь означает, что C( n) есть действие, производимое некоей машиной Тьюринга над числом n. Иными словами, число п наносится на ленту и подается на вход машины, после чего машина самостоятельно выполняет вычисления. Если вас почему-либо не устраивает концепция «машины Тьюринга», вообразите себе самый обыкновенный универсальный компьютер и считайте n«данными», необходимыми для работы какой-нибудь программы. Нас в данном случае интересует лишь одно: при любом ли значении nможет завершиться работа такого компьютера.
Для того чтобы пояснить, что именно понимается под вычислением, зависящим от натурального числа n, рассмотрим два примера:
(F)найти число, не являющееся суммой квадратов nчисел,
и
(G)найти нечетное число, являющееся суммой nчетных чисел.
Припомнив, о чем говорилось выше, мы без особого труда убедимся, что вычисление (F)завершается толькопри n= 0, 1, 2 и 3 (давая в результате, соответственно, 1, 2, 3 и 7), тогда как вычисление (G)вообще не завершается ни при каком значении n. Вздумай мы действительно доказать, что вычисление (F)не завершается при n, равном или большем 4, нам понадобилась бы более или менее серьезная математическая подготовка (по крайней мере, знакомство с доказательством Лагранжа); с другой стороны, тот факт, что ни при каком nне завершается вычисление (G), вполне очевиден. Какими же процедурами располагают математики для установления незавершаемой природы таких вычислений в общем случае? Можно ли сами эти процедуры представить в вычислительной форме?
Предположим, что у нас имеется некая вычислительная процедура А, которая по завершении [9] дает нам исчерпывающее доказательство того, что вычисление C( n) действительно никогда не заканчивается. Ниже мы попробуем вообразить, что A включает в себя всеизвестные математикам процедуры, посредством которых можно убедительно доказать, что то или иное вычисление никогда не завершается. Соответственно, если в каком-то конкретном случае завершается процедура A, то мы получаем, в рамках доступного человеку знания, доказательство того, что рассматриваемое конкретное вычисление никогда не заканчивается. Большая часть последующих рассуждений не потребует участия процедуры Aименно в такой роли, так как они посвящены, в основном, математическим умопостроениям. Однако для получения окончательного заключения Gнам придется-таки придать процедуре Aсоответствующий статус.
9
Здесь я предполагаю, что если процедура Авообще завершается, то это свидетельствует об успешном установлении факта незавершаемости C( n). Если же А«застревает» по какой-либо иной, нежели достижение «успеха», причине, то это означает, что в данном случае процедура Aкорректно завершиться не может. См. далее по тексту возражения Q3и Q4, а также Приложение А.
Я, разумеется, не требую, чтобы посредством процедуры Aвсегда можно было однозначно установить, что вычисление C( n) нельзя завершить (в случае, если это действительно так); однако я настаиваю на том, что неверных ответов Aне дает, т.е. если мы с ее помощью пришли к выводу, что вычисление C( n) не завершается, значит, так оно и есть. Процедуру A, которая и в самом деле всегда дает верный ответ, мы будем называть обоснованной.
Следует отметить, что если процедура Aоказывается в действительности необоснованной, то этот факт, в принципе, можно установить с помощью прямого вычисления — иными словами, необоснованную процедуру Aможно
Для того чтобы процедуру Aможно было применять к вычислениям в общем случае, нам потребуется какой-нибудь способ маркировки различных вычислений C( n), допускаемый A. Все возможные вычисления Cможно, вообще говоря, представить в виде простой последовательности
C 0, C 1, C 2, C 3, C 4, C 5, …,
т.е. q– e вычисление при этом получит обозначение C q. В случае применения такого вычисления к конкретному числу n будем записывать
C 0( n), C 1( n), C 2( n), C 3( n), C 4( n), C 5( n), ….
Можно представить, что эта последовательность задается, скажем, как некий пронумерованный ряд компьютерных программ. (Для большей ясности мы могли бы, при желании, рассматривать такую последовательность как ряд пронумерованных машин Тьюринга, описанных в НРК; в этом случае вычисление C q( n) представляет собой процедуру, выполняемую q– й машиной Тьюринга T qнад числом n.) Здесь важно учитывать следующий технический момент: рассматриваемая последовательность является вычислимой— иными словами, существует одно-единственное [10] вычисление C •, которое, будучи выполнено над числом q, дает в результате C q, или, если точнее, выполнение вычисления C •над паройчисел q, n(именно в таком порядке) дает в результате C q( n).
10
Собственно, точно такой же результат достигается посредством процедуры, выполняемой универсальной машиной Тьюринга над парой чисел q, n; см. Приложение Аи НРК, с. 51-57.
Можно полагать, что процедура Aпредставляет собой некое особое вычисление, выполняя которое над парой чисел q, n, можно однозначно установить, что вычисление C q( n), в конечном итоге, никогда не завершится. Таким образом, когда завершаетсявычисление A, мы имеем достаточное доказательство того, что вычисление C q( n) завершить невозможно. Хотя, как уже говорилось, мы и попытаемся вскоре представить себе такую процедуру A, которая формализует всеизвестные современной математике процедуры, способные достоверно установить невозможность завершения вычисления, нет никакой необходимости придавать Aтакой смысл прямо сейчас. Пока же процедурой Aмы будем называть любой обоснованныйнабор вычислительных правил, с помощью которого можно установить, что то или иное вычисление C q( n) никогда не завершается. Поскольку выполняемое процедурой А вычисление зависит от двух чисел qи n, его можно обозначить как A( q, n) и записать следующее утверждение: