Часть I

Почему для понимания разума необходима новая физика?. Невычислимость сознательного мышления

3. О невычислимости в математическом мышлении


...

3.20. Возможность ограничиться конечным числом ☆M-утверждений

Есть, впрочем, возможность именно эту конкретную проблему разрешить и сузить область рассмотрения до конечного множества различных ☆M-утверждений. Само доказательство несколько громоздко, однако основная идея заключается в том, что следует рассматривать только те Π1-высказывания, спецификации которых являются «краткими» в некотором вполне определенном смысле. Конкретная степень необходимой «краткости» зависит от того, насколько сложное описание системы механизмов M нам необходимо. Чем сложнее описание M, тем «длиннее» допускаемые к рассмотрению Π1-высказывания. «Максимальная длина» задается неким числом c, которое можно определить из степени сложности правил, определяющих формальную систему Q'M(M). Смысл в том, что при переходе к гёделевскому предположению для этой формальной системы — которую нам, вообще говоря, придется слегка модифицировать — мы получим утверждение, сложность которого будет лишь немногим выше, нежели сложность такой модифицированной системы. Таким образом, проявив должную осторожность при выборе числа c, мы можем добиться того, что и гёделевское предположение будет также «кратким». Это позволит нам получить требуемое противоречие, не выходя за пределы конечного множества «кратких» Π1-высказываний.

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

Нам понадобится несколько модифицировать формальную систему Q'M(M), приведя ее к виду Q'M(M, c) — для краткости я буду обозначать ее просто как Q(c) (отброшенные обозначения в данной ситуации несущественны и лишь добавляют путаницы и громоздкости). Формальная система Q(c) определяется следующим образом: при построении этой системы допускается принимать в качестве «безошибочных» только те ☆M-утверждения, степень сложности которых (задаваемая описанным выше числом ρ) меньше c, где c есть некоторое должным образом выбранное число, подробнее о котором я расскажу чуть ниже. Для «безошибочных» ☆M-утверждений, удовлетворяющих неравенству ρ < c, я буду использовать обозначение «√краткие ☆M-утверждения». Как и прежде, множество действительных теорем формальной системы Q(c) будет включать в себя не только √краткие ☆M-утверждения, но также и утверждения, получаемые из √кратких ☆M-утверждений посредством стандартных логических операций (позаимствованных, скажем, из исчисления предикатов). Хотя количество теорем системы Q(c) бесконечно, все они выводятся с помощью обыкновенных логических операций из конечного множества √кратких ☆M-утверждений. Далее, поскольку мы ограничиваем рассмотрение конечным множеством, мы вполне можем допустить, что функции T, L и N постоянны (и принимают, скажем, наибольшие значения на конечном интервале ρ). Таким образом, формальная система Q(c) задается лишь четырьмя постоянными c, T, L, N и общей системой механизмов M, определяющих поведение робота.

Отметим существенный для наших рассуждений момент: гёделевская процедура строго фиксирована и не нуждается в увеличении сложности выше некоторого определенного предела. Гёделевским предположением G(H) для формальной системы H является Π1-высказывание, степень сложности которого должна лишь на сравнительно малую величину превышать степень сложности самой системы H, причем эту величину можно определить точно.

Конкретности ради я позволю себе некоторое нарушение системы обозначений и буду вкладывать в запись «G(H)» некий особый смысл, который может и не совпасть в точности с определением, данным в §2.8. В формальной системе H нас интересует лишь ее способность доказывать Π1-высказывания. В силу этой своей способности система H дает нам алгебраическую процедуру A, с помощью которой мы можем в точности установить (на основании завершения выполнения A) справедливость тех Π1-высказываний, формулировка которых допускается правилами системы H. А под Π1-высказыванием понимается утверждение вида «действие машины Тьюринга Tp(q) не завершается» — здесь и далее мы будем пользоваться специальным способом маркировки машин Тьюринга, описанным в Приложении А (или в НРК, глава 2). Мы полагаем, что процедура A выполняется над парой чисел (p, q), как в §2.5. Таким образом, собственно вычисление А(p, q) завершается в том и только в том случае, если в рамках формальной системы H возможно установить справедливость того самого Π1-высказывания, которое утверждает, что «действие Tp(q) не завершается». С помощью описанной в §2.5 процедуры мы получили некое конкретное вычисление (обозначенное там как «Ck(k)»), а вместе с ним, при условии обоснованности системы H, и истинное Π1-высказывание, которое системе H оказывается «не по зубам». Именно это Π1-высказывание я буду теперь обозначать через G(H). Оно существенно эквивалентно (при условии достаточной обширности H) действительному утверждению «система H непротиворечива», хотя в некоторых деталях эти два утверждения могут и не совпадать (см. §2.8).

Пусть α есть степень сложности процедуры A (по определению, данному в §2.6, в конце комментария к возражению Q8) — иными словами, количество знаков в двоичном представлении числа α, где A = Tα. Тогда, согласно построению, представленному в явном виде в Приложении А, находим, что степень сложности η утверждения G(H) удовлетворяет неравенству η < α + 210 Iog2(α + 336). Для нужд настоящего рассуждения мы можем определить степень сложности формальной системы H как равную степени сложности процедуры A, т.е. числу α. Приняв такое определение, мы видим, что «излишек» сложности, связанный с переходом от H к G(H), оказывается еще меньше, чем и без того относительно крохотная величина 210 Iog2(α + 336).

Далее нам предстоит показать, что если H = Q(c) при достаточно большом c, то η < c. Отсюда, соответственно, последует, что и Π1-высказывание G(Q(c)) должно оказаться в пределах досягаемости системы Q (с) при условии, что роботы принимают G(Q(c)) с ☆-убежденностью. Доказав, что cγ + 210 log2(γ + 336), мы докажем и то, что γ < c; буквой γ мы обозначили значение α при H = Q(c). Единственная возможная сложность здесь обусловлена тем обстоятельством, что сама величина γ зависит от c, хотя и не обязательно очень сильно. Эта зависимость γ от c имеет две различных причины. Во-первых, число c являет собой явный предел степени сложности тех Π1-высказываний, которые в определении формальной системы Q(c) называются «безошибочными ☆M-утверждениями»; вторая же причина происходит из того факта, что система Q(c) явным образом обусловлена выбором чисел T, L и N, и можно предположить, что для принятия в качестве «безошибочного» ☆M-утверждения большей сложности необходимы какие-то более жесткие критерии.

Относительно первой причины зависимости γ от c отметим, что описание действительной величины числа c необходимо задавать в явном виде только однажды (после чего внутри системы достаточно обозначения c). Если при задании величины с используется чисто двоичное представление, то (при больших c) такое описание дает всего-навсего логарифмическую зависимость γ от c (поскольку количество знаков в двоичном представлении натурального n равно приблизительно log2n). Вообще говоря, учитывая, что число с интересует нас лишь в качестве возможного предела, точное значение которого находить вовсе не обязательно, мы можем поступить гораздо более остроумным образом. Например, число 22...2 с s показателями можно задать с помощью s символов или около того, и вовсе нетрудно подыскать примеры, в которых величина задаваемого числа возрастает с ростом s еще быстрее. Сгодится любая вычислимая функция от s. Иными словами, для того чтобы задать предел c (при достаточно большом значении c), необходимо всего лишь несколько символов.

Что касается второй причины, т.е. зависимости от c чисел T, L и N, то, в силу вышеизложенных соображений, представляется очевидным, что для задания величин этих чисел (в особенности, их возможных предельных значений) совершенно не требуется, чтобы количество знаков в их двоичном представлении возрастало так же быстро, как c; более чем достаточно будет и, скажем, обыкновенной логарифмической зависимости от c. Следовательно, мы с легкостью можем допустить, что зависимость величины γ + 210 log2(γ + 336) от c является не более чем грубо логарифмической, а также устроить так, чтобы само число c всегда было больше этой величины.

Согласимся с таким выбором с и будем в дальнейшем вместо Q(c) записывать Q*. Итак, Q* есть формальная система, теоремами которой являются все математические высказывания, какие можно вывести из конечного количества √кратких ☆M-утверждений, используя стандартные логические правила (исчисление предикатов). Количество этих ☆M-утверждений конечно, поэтому разумным будет предположить, что для гарантии их действительной безошибочности вполне достаточно некоторого набора постоянных T, L и N. Если роботы верят в это с ☆M-убежденностью, то они, несомненно, ☆M-заключат, что гёделевское предположение G(Q*) также истинно на основании гипотезы M, поскольку является Π1-высказыванием меньшей, нежели c, сложности. Рассуждение для получения утверждения G(Q*) из ☆M-убежденности в обоснованности формальной системы Q* достаточно просто (в сущности, я его уже привел), так что с присвоением этому утверждению статуса ☆M проблем возникнуть не должно. То есть само G(Q*) также должно быть теоремой системы Q*. Это, однако, противоречит убежденности роботов в обоснованности Q*. Таким образом, упомянутая убежденность (при условии справедливости гипотезы M и достаточно больших числах T, L и N) оказывается несовместимой с убежденностью в том, что поведением роботов действительно управляют механизмы M, — а значит, механизмы M поведением роботов управлять не могут.

Как же роботы могут удостовериться в том, что были выбраны достаточно большие числа T, L и N? Никак. Вместо этого они могут выбрать некоторый набор таких чисел и попробовать допустить, что те достаточно велики, — и прийти в результате к противоречию с исходным предположением, согласно которому их поведение обусловлено набором механизмов M. Далее они вольны предположить, что достаточным окажется набор из несколько больших чисел, — снова прийти к противоречию и т.д. Вскоре они сообразят, что к противоречию они приходят при любом выборе значений (вообще говоря, здесь нужно учесть, помимо прочего, небольшой технический момент, суть которого состоит в том, что при совершенно уже запредельных значениях T, L и N значение c также должно будет несколько подрасти — однако это неважно). Таким образом, получая один и тот же результат вне зависимости от значений T, L и N, роботы — равно как, по всей видимости, и мы — приходят к заключению, что в основе их математических мыслительных процессов не может лежать познаваемая вычислительная процедура M, какой бы она ни была.