Структура реальности. Наука параллельных вселенных

Как я уже сказал, такая универсальность была впервые изучена не физиками, а математиками. Они пытались придать строгость интуитивному понятию «вычисления» («расчета» или «доказательства») в математике. Они не учитывали, что математическое вычисление – это физический процесс (в частности, как я уже объяснил, процесс создания в виртуальной реальности), поэтому путем математического рассуждения невозможно определить, что можно вычислить математически, а что нельзя. Это полностью зависит от законов физики. Но вместо того, чтобы пытаться вывести свои результаты из законов физики, математики постулировали абстрактные модели «вычисления» и определили «расчет» и «доказательство» на основе этих моделей. (Я вернусь к этой интересной ошибке в главе 10.) Вот так и получилось, что за несколько месяцев 1936 года три математика – Эмиль Пост[21], Алонзо Чёрч[22] и, главное, Алан Тьюринг – независимо друг от друга создали первые абстрактные схемы универсальных компьютеров. Каждый из них считал, что его модель «вычисления» действительно правильно формализует традиционное интуитивное понятие математического «вычисления». Следовательно, каждый из них также полагал, что его модель эквивалентна (имеет тот же репертуар) любой другой разумной формализации подобной интуиции. Сейчас это известно как гипотеза Чёрча – Тьюринга.

Модель вычисления Тьюринга и концепция природы проблемы, которую он решал, была наиболее близка к физике. Его абстрактный компьютер, машина Тьюринга, представлял собой бумажную ленту, разделенную на квадраты, причем на каждом квадрате был написан один из конечного числа легко различимых символов. Вычисление осуществлялось следующим образом: на каждом шаге считывался один квадрат, затем лента перемещалась вперед или назад и производилось стирание или запись одного из символов в соответствии с простыми недвусмысленными правилами. Тьюринг доказал, что один конкретный компьютер такого типа, универсальная машина Тьюринга, имеет объединенный репертуар всех других машин Тьюринга. Он предположил, что этот репертуар в точности состоит из «всех функций, которые естественно полагать вычислимыми». Он имел в виду вычислимость математиками.

Однако математики – это достаточно нетипичные физические объекты. Почему мы должны допускать, что воспроизведение их в ходе выполнении вычислений – предел вычислительных задач? Оказывается, что не должны. Как я объясню в главе 9, квантовые компьютеры могут выполнять вычисления, которые ни один человек-математик никогда, даже в принципе, не сможет выполнить. В работе Тьюринга неявно выражено его ожидание того, что функции, которые «естественно полагать вычислимыми», могли бы, по крайней мере в принципе, быть вычисленными и в природе. Это ожидание эквивалентно более сильной, физической версии гипотезы Чёрча – Тьюринга. Математик Роджер Пенроуз[23] предложил назвать его принципом Тьюринга.

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

Существует абстрактный универсальный компьютер, репертуар которого включает любое вычисление, выполнимое каким-либо физически возможным объектом.

Тьюринг считал, что «универсальный компьютер», о котором идет речь, – это универсальная машина Тьюринга. Чтобы принять во внимание более широкий репертуар квантовых компьютеров, я сформулировал принцип в такой форме, которая не указывает, какой именно «абстрактный компьютер» выполняет эту работу.