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

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

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

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

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

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