Девид Дойч - Структура реальности

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

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

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