Структура реальности - Дойч Дэвид (читать книги онлайн бесплатно без сокращение бесплатно txt) 📗

Одно из сделанных Геделем допущений было традиционным: доказательство может иметь только конечное число этапов. Интуитивное доказательство этого допущения состоит в том, что мы конечные существа и никогда не смогли бы постичь буквально бесконечное число утверждений. Кстати, именно эта интуиция стала причиной беспокойства многих математиков, когда в 1976 году Кеннет Эппел и Вольфганг Хакен использовали компьютер для доказательства знаменитой «гипотезы четырех цветов» (о том, что, используя всего четыре разных цвета, любую карту, нарисованную на плоскости, можно раскрасить так, что никакие два примыкающих района не будут иметь одинаковый цвет). Программа требовала сотни часов машинного времени, что означало, что этапы доказательства, если оно было бы записано, не смог бы прочитать ни один человек за много жизней, не говоря уже о том, чтобы признать его самоочевидным. «Следует ли воспринимать слово компьютера как то, что гипотеза четырех цветов доказана?» — задавались вопросом скептики — хотя им и в голову никогда не приходило составить каталог всех импульсов всех нейронов своего собственного мозга при принятии относительно «простого» доказательства.

Такое же беспокойство может показаться более оправданным, будучи примененным к предполагаемому решению с бесконечным числом этапов. Но что такое «этап» и что такое «бесконечный»? В пятом веке до н.э. Зенон из Элеи на основе похожей интуиции пришел к выводу, Что Ахиллес никогда не обгонит черепаху, если у черепахи будет преимущество на старте. Как-никак, к тому времени, когда Ахиллес поравняется с черепахой, она еще немножко продвинется вперед. К тому времени, когда он достигнет этой точки, она продвинется еще чуть-чуть и так до бесконечности. Таким образом, эта процедура «обгона» потребует от Ахиллеса выполнения бесконечного количества этапов обгона, которое он, будучи конечным существом, предположительно выполнить не сможет. Но то, что Ахиллес сможет сделать, невозможно обнаружить с помощью чистой логики. Это полностью зависит от того, что он сможет сделать в соответствии с управляющими законами физики. И если эти законы скажут, что он обгонит черепаху, то он ее обгонит. В соответствии с классической физикой обгон требует бесконечного количества этапов вида «переход на настоящее место нахождения черепахи». В этом смысле данное действие является вычислительно бесконечным. Точно так же, если рассматривать как доказательство то, что одна абстрактная величина становится больше другой при применении данного набора действий, то это доказательство с бесконечным количеством этапов. Однако соответствующие законы обозначают это доказательство как физически конечный процесс — и только это имеет значение.

Интуиция Геделя относительно этапов и конечности, насколько нам известно, действительно накладывает некоторые физические ограничения на процесс доказательства. Квантовая теория требует дискретных этапов, и ни один из известных способов взаимодействия физических объектов не позволил бы бесконечному количеству этапов превзойти измеримый вывод. (Однако, могло бы оказаться возможным, что за всю историю вселенной было бы выполнено бесконечное количество этапов — я объясню это в главе 14). Классическая физика, даже будь она истинной (что исключено), не согласилась бы с такого рода интуицией. Например, непрерывное движение классических систем предусмотрело бы «аналогичное» вычисление, в котором было бы не слишком много этапов и которое обладало бы репертуаром, существенно отличающимся от машины Тьюринга. Известны некоторые примеры хитросплетенных классических законов, в соответствии с которыми бесконечный объем вычислений (бесконечный в соответствии с нормами машины Тьюринга или квантового компьютера) можно было бы выполнить с помощью физически конечных методов. Безусловно, классическая физика несовместима с результатами бесчисленных экспериментов, поэтому размышление о том, какими «были бы» «действительные» классические законы физики, носит весьма искусственный характер: однако эти примеры показывают, что никто не может доказать, независимо от знания физики, что доказательство должно состоять из конечного числа этапов. Эти же соображения применимы к интуиции о том, что должно быть конечное количество правил вывода и что они должны быть «применимы напрямую». Ни одно из этих требований не имеет смысла для абстрактного: это физические требования. Гильберт в своем влиятельном эссе «On the Infinite» [16] со знанием дела высмеял идею реальности требования «конечного количества ступеней». Однако вышеуказанный аргумент показывает, что он ошибался: это требование реально, и оно следует только из физической интуиции самого Гильберта и других математиков.

По крайней мере, одно из направлений интуиции Геделя относительно доказательства, оказывается, было ошибочным; к счастью, это никак не влияет на доказательства его теорем. Он унаследовал это направление из предыстории греческой математики, и оно не вызывало сомнений ни у одного поколения математиков до тех пор, пока в 1908 году открытия в области квантовой теории вычислений не доказали его ложность. Это направление интуиции заключается в том, что доказательство — это конкретная разновидность объекта, а именно, последовательность утверждений, которая подчиняется правилам вывода. Я уже говорил о том, что доказательство лучше рассматривать не как объект, а как процесс, разновидность вычислений. Однако в классической теории доказательства или вычисления это не делает фундаментальной разницы по следующей причине. Если мы можем пройти через процесс доказательства, мы можем только с небольшим дополнительным усилием вести запись всего важного, что происходит во время этого процесса. Эта запись, физический объект, составит доказательство в смысле последовательности утверждений. II наоборот, если бы у нас была такая запись, мы могли бы прочитать ее, проверить, удовлетворяет ли она правилам вывода, и в процессе этого мы докажем вывод. Другими словами, в классическом случае преобразование процессов доказательства и объектов доказательства — это всегда легковычисляемая задача.

Теперь давайте рассмотрим некоторое математическое вычисление, которое является трудновыполнимым на всех классических компьютерах, но предположим, что квантовый компьютер легко может выполнить это вычисление, задействовав интерференцию между, скажем. 10500 вселенными. Чтобы прояснить это, пусть вычисление будет таково, что ответ после его получения (в отличие от результата разложения на множители) невозможно будет проверить с помощью легкообрабатываемых вычислений. Процесс программирования квантового компьютера для получения вычислений такого рода, обработки программы и получения результата составляет доказательство того, что математическое вычисление имеет именно этот частный результат. Но в этом случае не существует способа записать все, что произошло во время процесса доказательства, потому что большая часть этого произошла в других вселенных, и измерение состояния вычисления изменило бы интерференционные свойства и тем самым лишило бы доказательство обоснованности. Таким образом, создание старомодного объекта доказательства было бы невозможно; более того, во вселенной, как мы ее знаем, далеко не достаточно материала, чтобы составить такой объект, поскольку в этом доказательстве этапов было бы больше, чем существует атомов в известной вселенной. Этот пример показывает, что из-за возможности квантового вычисления два понятия доказательства не эквивалентны. Интуиция доказательства как объекта не охватывает все способы, с помощью которых можно доказать математическое утверждение в реальности.

И опять мы видим неадекватность традиционного математического метода получения определенности через попытки исключить каждый возможный источник неопределенности или ошибки из нашей интуиции до тех пор, пока не останется только самоочевидная истина. Именно это и сделал Гедель. Именно это делали Черч, Пост и особенно Тьюринг, когда они пытались интуитивно постичь свои универсальные модели вычисления. Тьюринг надеялся, что его абстрактная бумажная модель настолько проста, настолько открыта и четко определена, что не зависит ни от каких допущений относительно физики, которые можно было бы исказить постижимым образом, и, следовательно, она может стать основой абстрактной теории вычисления, независимой от лежащей в ее основе физики. «Он считал, — как однажды выразился Фейнман, — что он понял бумагу». Но он ошибался. Реальная, квантово-механическая бумага очень отличается от абстрактного материала, используемого машиной Тьюринга. Машина Тьюринга является всецело классической, она не принимает во внимание возможность того, что на бумаге могут быть написаны различные символы в различных вселенных и что они могут интерферировать друг с другом. Безусловно, искать интерференцию между различными состояниями бумажной центы непрактично. Но дело в том, что интуиция Тьюринга, из-за содержания в ней ложных допущений из классической физики, заставила его удалить те вычислительные свойства его гипотетической машины, которые он намеревался сохранить. Именно поэтому результирующая модель вычисления была неполной.