Квантовые вычисления со времен Демокрита - Скотт Ааронсон

Хорошо, а есть ли у нас еще что-нибудь, что также дает ощущение абсолютной уверенности? Правильно, математика! Кстати говоря, я считаю, что именно сходством между математикой и субъективным восприятием в значительной степени объясняются «квазимистические» наклонности многих математиков. (Я уже слышу, как некоторые математики морщатся. Простите!) Физикам полезно понимать: когда говоришь с математиком, дело не обязательно в том, что он боится реального мира и потому уходит в этакую интеллектуальную мастурбацию. Может быть, для этого человека реальный мир просто никогда не был особенно реален!

Вот что я имею в виду. Возьмите компьютерное доказательство гипотезы о четырех красках, которую я уже мельком упоминал. Это доказательство разрешило великую математическую задачу, державшуюся целый век, но сделало это посредством сведения ее к скучному перечислению тысяч конкретных случаев. Почему некоторые математики недовольны этим доказательством или, по крайней мере, надеются на появление другого, лучшего? Потому что компьютер «мог сделать ошибку»? Ну, это довольно слабый аргумент, поскольку доказательство было проверено несколькими независимыми группами программистов с использованием разного оборудования и программного обеспечения; к тому же человек и сам делает множество ошибок!

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

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

1. Непосредственно воспринимаемая уверенность в том, что сами они обладают сознанием — что они воспринимают цвета, звуки, положительные целые числа и т. п., независимо от того, делают ли это все остальные, и

2. Уверенность в том, что если бы они были всего лишь вычислительным процессом, то они не могли бы обладать сознанием в этом смысле.

К примеру, я считаю, что возражения Пенроуза против сильного ИИ базируются именно на этих двух факторах. Я считаю, что его критика теоремы Гёделя — всего лишь занавесочка на окне, добавленная позже.

Для тех, кто думает так (и я сам — в соответствующем настроении), признание за роботом права на сознание представляется в каком-то странном смысле эквивалентным отрицанию собственного сознания. Существует ли достойный выход из этой дилеммы, или, иными словами, хоть какой-нибудь выход, не основанный на совершенно шовинистических двойных стандартах, когда к самим себе применяются одни правила, а к роботам — другие?

Мне больше всего нравится выход, который продвигает философ Дэвид Чалмерс[22]. Суть того, что предлагает Чалмерс, состоит в «философской редукции NP-полноты», то есть в сведении одной загадки к другой. Он говорит, что если компьютеры когда-нибудь научатся имитировать людей во всех наблюдаемых отношениях, то мы будем вынуждены рассматривать их как обладающие сознанием, в точности по тем же причинам, по которым мы рассматриваем окружающих нас людей как обладающих сознанием. Что же касается того, как они могут обладать сознанием, — ну, мы при этом будем понимать это точно так же хорошо или точно так же плохо, как мы понимаем, как кучка нейронов может обладать сознанием. Да, это загадка, но в данном случае одна загадка, кажется, не так уж сильно отличается от другой.

Загадки

• [Почти хорошо определенная загадка.] Можем ли мы считать без потери общности, что компьютерная программа имеет доступ к собственному исходному коду?

• [Расплывчатая, плохо определенная загадка.] Если бы то, что до XIX века называлось водой, оказалось CH4, а не H2O, что это было бы — по-прежнему вода или что-то другое?

Ответы на упражнения из предыдущей главы

Вспомним, что BB(n), или «n-е число Делового Бобра», — это наибольшее число шагов, которые машина Тьюринга с n-состояниями может сделать на чистой первоначально ленте, прежде чем остановится.

Первой задачей было доказать, что BB(n) растет быстрее, чем какая бы то ни было вычислимая функция.

Предположим, что существует вычислимая функция f(n), такая, что f(n) > BB(n) для любого n. Тогда, имея машину Тьюринга M с n-состояниями, мы можем сначала вычислить f(n), а затем смоделировать работу M вплоть до f(n) — го шага. Если M не остановилась до этого момента, то мы можем быть уверены, что она не остановится никогда, потому что f(n) больше максимального числа шагов, которые может сделать произвольная машина с n-состояниями. Но это дает нам способ решить проблему остановки, что, как мы уже знаем, невозможно. Следовательно, функция f не существует.

Таким образом, функция BB(n) растет очень, очень, очень быстро. (На случай, если вам любопытно, приведу несколько ее первых значений, вычисленных неленивыми людьми, у которых слишком много свободного времени: BB(1) = 1, BB(2) = 6, BB(3) = 21, BB(4) = 107, BB(5) ≥ 47 176 870. Разумеется, эти значения зависят от конкретных деталей того, как определены машины Тьюринга.)

Второй задачей было определить, является ли

вычислимым действительным числом. Иными словами, существует ли алгоритм, который на основе положительного целого k выдает рациональное число S', такое, что |S — S'| < 1/k?

Что, эта задача оказалась посложнее для вас? Хорошо, давайте заглянем в ответ. Ответ отрицательный: это число не является вычислимым. Потому что, если предположить его вычислимость, мы получим алгоритм для вычисления самого BB(n), что, как мы знаем, невозможно.

Примем по индукции, что мы уже вычислили BB(1), BB(2),…, BB(n — 1). Тогда рассмотрим сумму «членов высшего порядка»:

Если S вычислимо, то Sn тоже должно быть вычислимым. Но это означает, что мы можем аппроксимировать Sn с точностью до 1/2, 1/4, 1/8 и так далее, до тех пор, пока интервал, в котором мы ограничили Sn, перестанет включать в себя 0. Когда это произойдет, мы получим верхнюю оценку для 1/Sn. Поскольку 1/BB(n + 1), 1/BB(n + 2) и т. п. намного меньше, чем 1/BB(n), любая верхняя оценка для 1/Sn немедленно выдает верхнюю оценку также и для BB(n). Но, получив верхнюю оценку для BB(n), мы можем вычислить и сам BB(n) путем простого моделирования всех машин Тьюринга