Теория вычислительных машин широко развивалась на протяжении последних нескольких десятилетий. Интуитивно вычислительная машина – это любая физическая система, динамическая эволюция которой переводит ее от одного из множества «входных» состояний к одному из множества выходных состояний. Эти состояния помечены некоторым каноническим образом, машина готовится в состоянии с заданной меткой входа, и затем, вслед за некоторым движением, измеряются выходные состояния. Для классической детерминированной системы измеренная метка выхода есть определенная функция $f$ заданной входной метки; более того, значение этой метки может быть в принципе измерено внешним наблюдателем («пользователем»), и говорят, что машина «вычисляет» функцию $f$.

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

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

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

В только что описанном смысле данная машина $M$ вычисляет не более одной функции. Тем не менее не должно быть существенного различия между изменением входного состояния, в котором готовится $M$, и систематическим изменением устройства $M$ так, что она становится другой машиной $M^{\prime}$, вычисляющей другую функцию. Чтобы формализовать такие операции, часто полезно рассматривать машины с двумя входами, подготовка одного из которых составляет «программу», определяющую то, какая функция другого входа должна вычисляться. Каждой такой машине $M$ соответствует множество $C(M) \ll M$-вычислимых функций». Функция $f-M$-вычислима, если $M$ может вычислить $f$, когда подготовлена некоторая программа.

Множество $C(M)$ может быть расширено увеличением множества изменений в устройстве $M$, которые размечены как возможные $M$-программы. По двум данным машинам $M$ и $M^{\prime}$ можно построить составную машину, множество вычислимых функций которой содержит объединение $C(M)$ и $C\left(M^{\prime}\right)$.
Не существует чисто логических причин, по которым нельзя до бесконечности строить все более мощные вычислительные машины и по которым существует какая-либо функция, которая находится за пределами вычислимого множества любой физически возможной машины. Но хотя логика и не запрещает физическое вычисление произвольных функций, кажется, что такой запрет накладывает физика. Как хорошо известно, разработчик вычислительной машины быстро достигает точки, когда добавление нового оборудования не меняет множество функций, вычислимых машиной (при идеализации неограниченности памяти); более того, для функций, отображающих множество целых чисел $\mathbb{Z}$ в себя, множество $C(M)$ всегда содержится в $C(\mathcal{T})$, где $\mathcal{T}$ универсальная вычислительная машина Тьюринга (Тьюринг, 1936). Само $C(\mathcal{T})$, также известное как множество всех частично-рекурсивных функций, перечислимо и, следовательно, бесконечно меньше, чем множество всех функций из $\mathbb{Z}$ в $\mathbb{Z}$.

Чёрч (1936) и Тьюринг (1936) предположили, что эти ограничения на то, что может быть вычислено, вызваны не состоянием дел в конструировании вычислительных машин или нашими способностями в изобретении моделей вычислений, а являются универсальными. Это называется гипотезой Чёрча-Тьюринга; по Тьюрингу,
Любая функция, «вычислимая в естественном» смысле, может быть вычислена универсальной машиной Тьюринга.
Обычный нефизический подход к (1.1) интерпретирует это как квазиматематическое предположение о том, что все возможные формализации интуитивного математического понятия «алгоритм» или «вычисление» эквивалентны друг другу. Но мы увидим, что это может также рассматриваться как утверждение нового физического принципа, который я буду называть принципом Чёрча-Тьюринга, чтобы отличить его от других следствий и переформулировок утверждения (1.1). Гипотеза (1.1) и другие формулировки, которые существуют в литературе (см. интересное обсуждение разнообразных версий, Хофштадтер (Hofstadter), 1979), очень туманны в сравнении с такими физическими принципами, как законы термодинамики или гравитационный принцип эквивалентности. Но ниже будет видно, что моя формулировка принципа Чёрча-Тьюринга (1.2) – очевидно физична и однозначна. Я покажу, что она имеет такой же эпистемологический статус, как и другие физические принципы.
Я предлагаю по-новому интерпретировать тьюрингово понятие «функций, вычислимых в естественном смысле», как функций, которые могут быть в принципе вычислены реальной физической системой. Действительно, трудно считать функцию вычислимой в естественном (природном) смысле, если она не вычислима Природой, и наоборот. Здесь я определю понятие полного моделирования (perfect simulation). Вычислительная машина $M$ может полностью моделировать физическую систему $\mathscr{Y}$ относительно данной разметки их входов и выходов, если для $M$ существует программа $\pi(\mathscr{Y})$, которая делает $M$ вычислительно эквивалентной $\mathscr{Y}$ относительно этой разметки. Другими словами, $\pi(\mathscr{Y})$ превращает $M$ в «черный ящик», функционально неотличимый от $\mathscr{Y}$.

Теперь я могу сформулировать физическую версию принципа Чёрча-Тьюринга:
Каждая конечно реализуемая физическая система может быть полностью моделирована универсальной модельной вычислительной машиной, оперирующей конечными средствами.
Эта формулировка и лучше определена, и имеет более физический смысл, чем собственный способ Тьюринга формулировать это (1.1), так как она ссылается исключительно на физические понятия, такие, как «измерение», «подготовка» ифизическая система», которые уже существуют в теории измерений. Она избегает терминологий типа «естественно определенный», которые не ложатся в существующую структуру физики.

Понятие «конечно реализуемые физические системы», о которых говорится в (1.2), должно включать любой физический объект, над которым возможно проведение эксперимента. «Универсальная вычислительная машина», с другой стороны, должна быть только идеализированной (но теоретически разрешенной) конечно определимой моделью. Разметки, на которые есть неявная ссылка в (1.2), также должны быть конечно определимыми.

Ссылка в (1.1) на особую универсальную машину (Тьюринга) по необходимости заменена в (1.2) на более общее требование того, что эта машина действует «конечными средствами». Понятие «конечных средств» может быть определено аксиоматически без ограничительных предположений о форме физических законов (ср. Ганди (Gandy), 1980). Поскольку мы можем представить, что действие вычислительной машины требует последовательности шагов, длительность которых имеет ненулевую нижнюю границу, то она действует «конечными средствами», если ( $i$ ) только конечная подсистема (хотя и не всегда одна и та же) находится в движении на протяжении одного шага, (ii) движение зависит только от состояний конечного числа подсистем и (iii) правило, которое определяет движение, может быть конечно задано в математическом смысле (например, как целое число). Машины Тьюринга удовлетворяют этим условиям, им также удовлетворяет и универсальный квантовый компьютер $\mathcal{Q}$ (см. §2).

Утверждение принципа Чёрча-Тьюринга (1.2) сильнее того, что необходимо для утверждения (1.1). Действительно, оно настолько сильно, что не удовлетворяется машиной Тьюринга в классической физике. Благодаря непрерывности классической динамики, возможные состояния классической системы необходимо составляют континуум. Но существует только счетное множество способов подготовки конечного входа для $\mathcal{T}$. Следовательно, $\mathcal{T}$ не может полностью моделировать любую классическую динамическую систему. (Хорошо изученная теория «моделирования» непрерывных систем посредством $\mathcal{T}$ рассматривает не полное моделирование в моем смысле, а последовательные дискретные аппроксимации.) В $\S 3$ я покажу, что с нашим современным знанием о взаимодействиях, существующих в природе, согласуется то, что каждая реальная (диссипативная) конечная система может быть полностью моделирована универсальным квантовым компьютером $\mathcal{Q}$. Таким образом, квантовая теория совместима с сильной формой (1.2) принципа Чёрча-Тьюринга.

Теперь я перехожу к моему аргументу о том, что (1.2) – эмпирическое утверждение. Обычный критерий эмпирического статуса теории – это возможность ее экспериментальной фальсифицируемости (Поппер (Popper), 1959), т.е. существование потенциальных наблюдений, которые противоречат ей. Но поскольку наиболее глубокие теории мы называем «принципами», то мы говорим об опытах только через другие теории, критерий фальсифицируемости должен в каждом случае применяться косвенно. Например, принцип сохранения энергии сам по себе не может противоречить какому-нибудь подходящему наблюдению, поскольку он не содержит определения того, как измерять энергию. Третий закон термодинамики, форма которого:
«Никакой конечный процесс не может уменьшить энтропию системы или температуру конечно реализуемой физической системы до нуля»,

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

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

Часто утверждается, что любая «разумная» физическая (в противоположность математической) модель вычисления, по крайней мере для детерминированного вычисления функций из $\mathbb{Z}$ в $\mathbb{Z}$, эквивалентна тьюринговой. Но это не так: нет никакой априорной причины, по которой физические законы должны следовать ограничениям математических процессов, которые мы называем «алгоритмами» (т.е. функциями $C(\mathcal{T})$ ). Хотя я не счел необходимым в данной статье это делать, но нет парадоксального или противоречивого в постулировании физических систем, которые вычисляют функции не из $C(\mathcal{T})$. Могут быть экспериментально проверяемые теории с таким эффектом: например, рассмотрим любое рекурсивно перечислимое нерекурсивное множество (например, множество целых чисел, представляющих программы для завершающихся алгоритмов на данной машине Тьюринга). В принципе, физическая теория могла бы иметь среди своих следствий то, что некоторое физическое устройство $\mathscr{F}$ может вычислить за определенное время, принадлежит ли произвольное целое число этому множеству. Эта теория была бы экспериментально опровергнута, если бы более простой компьютер тьюрингового типа, запрограммированный для того, чтобы перечислить это множество, когда-нибудь не согласился бы с $\mathscr{F}$. (Конечно, теория делала бы и другие предсказания, иначе она не была бы нетривиально проверяемой, и ее структура была бы такой, что экзотические предсказания об $\mathscr{F}$ не могли бы естественно получаться из другого физического содержания. Все это логически возможно.)

С другой стороны, не очевидно а priori, что любая из известных рекурсивных функций вычислима в физической реальности. Причины того, почему мы находим возможным сконструировать, например, электронный калькулятор и почему мы можем выполнять арифметические действия в уме, не могут быть найдены в математике или логике. Причина состоит в том, что законы физики «оказались» такими, что разрешают существование физических моделей для операций арифметики, таких как сложение, вычитание и умножение. Если бы это было не так, то эти известные операции были бы невычислимыми функциями. Мы могли бы тем не менее знать о них и использовать их в математических доказательствах (которые изначально назывались бы «неконструктивными»), но мы не могли бы выполнить их.

Если динамика некоторых физических систем зависела бы от функции не из $C(\mathcal{T})$, то такие системы могли бы, в принципе, использоваться для вычисления этой функции. Чейтин (Chaitin) (1977) показал, как истинностные значения всех «интересных» не разрешимых по Тьюрингу утверждений данной формальной системы могут быть очень эффективно протабулированы с помощью первых нескольких значащих цифр одной физической константы.

Но если бы это было так, то можно было бы возразить, что мы бы об этом никогда не узнали, потому что мы не могли бы проверить точность «таблицы», предоставленной природой. Это заблуждение. Причина, по которой мы уверены в том, что машины, которые мы называем калькуляторами, на самом деле вычисляют арифметические функции, которые им предписано вычислять, не в том, что мы можем «проверить» их ответы, так как это крайне бесполезный процесс сравнения одной машины с другой. Quis custodiet custodias ipsos? ${ }^{1}$ Настоящая причина в том, что мы верим в детальную физическую теорию, которая была использована при их конструировании. Эта теория, включающая утверждение о том, что абстрактные функции арифметики реализованы в Природе, – эмпирическая.