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

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

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

Насколько эффективно можно передать данные аспекты реальности? Другими словами, какие вычисления можно практически выполнить за данное время и при данных финансовых возможностях? Это основной вопрос теории вычислительной сложности, которая, как я уже сказал, занимается изучением ресурсов, необходимых для выполнения данных вычислительных задач. Теория сложности все еще в достаточной степени не объединена с физикой и потому не дает много количественных ответов. Однако она достигла успеха в определении полезного приближенного различия между легко- и труднообрабатываемыми вычислительными задачами. Общий подход лучше всего проиллюстрировать на примере. Рассмотрим задачу умножения двух достаточно больших чисел, скажем. 4 220 851 и 2594209. Многие из нас помнят тот метод умножения, которому мы научились в детстве. Нужно по очереди перемножить каждую цифру одного числа на каждую цифру другого и, сложив результаты, дать окончательный ответ, в данном случае 10949769651859. Вероятно, многие не захотят признать, что эта утомительная процедура делает умножение «легко обрабатываемым» хоть в каком-то обыденном смысле этого слова. (В действительности, существуют более эффективные методы умножения больших чисел, но этот весьма нагляден). Однако с точки зрения теории сложности, которая имеет дело с массивными задачами, решаемыми компьютерами которые не подвержены скуке и почти никогда не ошибаются, этот метод определенно попадает в категорию «легко обрабатываемых».

В соответствии со стандартным определением для «легкости обработки» важно не действительное время, затрачиваемое на умножение конкретной пары чисел, а важен факт, что при применении того же самого метода даже к большим числам, время увеличивается не слишком резко. Возможно это удивит вас, но этот весьма косвенный метод определения легкости обработки очень хорошо работает на практике для многих (хотя и не всех) важных классов вычислительных задач. Например, при умножении нетрудно увидеть, что стандартный метод можно использовать для умножения чисел, скажем, в десять раз больших, Приложив совсем незначительные дополнительные усилия. Ради доказательства предположим, что каждое элементарное умножение одной цифры на другую занимает у определенного компьютера одну микросекунду (включая время, необходимое для сложения, переходов и других операций, сопровождающих каждое элементарное умножение). При умножении семизначных чисел 4220851 и 2594209 каждую из семи цифр первого числа нужно умножить на каждую из семи цифр второго числа. Таким образом, общее время, необходимое для умножения (если операции выполняются последовательно), будет равно семи, умноженному на семь, или 49 микросекундам. При введении чисел, примерно в десять раз больших, содержащих по восемь цифр, время, необходимое для их умножения, будет равно 64 микросекундам: увеличение составляет всего 31%.

Ясно, что числа из огромного диапазона – безусловно содержащего любые числа, которые когда-либо были измерены как численные значения физических переменных – можно перемножить за крошечную долю секунды. Таким образом, умножение действительно легко поддается обработке для любых целей в пределах физики (или, по крайней мере, в пределах существующей физики). Вероятно, за пределами физики могут появиться практические причины умножения гораздо больших чисел. Например, для шифровальщиков огромный интерес представляют произведения простых чисел, состоящих примерно из 125 цифр. Наша гипотетическая машина могла бы умножить два таких простых числа, получив произведение, состоящее из 250 цифр, примерно за одну сотую секунды. За одну секунду она могла бы перемножить два тысячезначных числа, а современные компьютеры легко могут осуществить более точный расчет этого времени. Только некоторые исследователи эзотерических областей чистой математики заинтересованы в выполнении таких непостижимо огромных умножений, однако, мы видим, что даже у них нет причины считать умножение трудно обрабатываемым.

Напротив, разложение на множители, по сути процесс, обратный умножению, кажется гораздо сложнее. В начале вводится одно число, скажем, 10949769651859, задача заключается в том, чтобы найти два множителя, меньших числа, произведение которых равно 10949769651859. Поскольку мы только что умножили эти числа, мы знаем, что в этом случае ответ будет 4220851 и 2594209 (и поскольку оба эти числа простые, это единственно правильный ответ). Но не обладая таким внутренним знанием, как мы нашли бы эти множители? В поисках простого метода вы обратитесь к детским воспоминаниям, но впустую, поскольку такого метода не существует.