Программируя Вселенную. Квантовый компьютер и будущее науки - Сет Ллойд

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

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

Я продолжал читать, находя все больше определений сложности, но все они были вариациями на тему необходимых усилий или количества информации. Несколько лет спустя я сделал доклад об этих различных мерах сложности на конференции в Институте Санта-Фе, основанном в середине 1980-х Джорджем Коуэном, Мюрреем Гелл-Манном и группой старших научных сотрудников из соседнего Лос-Аламоса, которых интересовало изучение правил, дающих начало сложным системам и лежащих в их основе. Этот доклад назывался «Тридцать одна мера сложности» (Thirty-one Measures of Complexity), причем «тридцать один» было хорошо известным намеком на количество сортов мороженого Baskin-Robbins. Хотя я не опубликовал доклад под этим названием, молва о нем распространилась в Интернете, и в течение многих лет доклад о 31 способе измерения сложности был моей самой часто запрашиваемой работой, несмотря на то что ее просто не существовало. (Несколько лет назад я, наконец, опубликовал этот список в виде статьи{15}, просто для того, чтобы больше не отвечать на электронные письма, в которых меня просили выслать эту несуществующую статью.) Кстати говоря, за время от прочтения доклада до публикации статьи количество способов измерения сложности выросло с тридцати одного до сорока двух. (Длина нового списка побудила писателя Джона Хоргана в книге «Конец науки» (The End of Science) утверждать, что наука о сложных системах оказалась несостоятельной, так как исследователи не смогли договориться даже о том, что такое сложность, уже не говоря о каких-либо серьезных исследованиях в этой области.)

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

Законы физики описывают компромиссы и взаимосвязи между измеримыми величинами, и законы сложности делают то же самое. Особенно полезным является компромисс между информацией и усилиями. Алгоритмическую информацию можно считать мерой содержания информации, а вычислительную сложность – мерой необходимых усилий. Рассмотрим количество усилий, необходимых для создания определенной строки битов – например, первого миллиона цифр числа p. Эти цифры можно получить с относительно небольшим количеством вычислительной сложности (всего несколько миллионов логических операций, что на обычном компьютере займет меньше секунды) с помощью программы длиной из миллиона с лишним знаков, которая говорит: «Напечатать 3,1415926…» Мы не знаем точной алгоритмической информации в первом миллионе цифр числа p (ведь алгоритмическая информация невычисляема), но можем искать верхнюю границу этой алгоритмической информации, создавая короткие программы, вычисляющие первый миллион цифр числа p. Например, в программе, которая вычисляет эти цифры с помощью математического метода представления в виде цепной дроби, может быть меньше 1000 знаков, но эта компактная программа будет вычислять первый миллион цифр числа p намного дольше, чем самая простая, но очень длинная программа типа «напечатать». Чтобы получить этот миллион цифр, ей потребуется выполнить миллиарды логических операций.

В начале 1980-х гг. Чарльз Беннетт предложил простое определение сложности, основанное на компромиссе между информацией и усилиями. Вслед за Соломоноффом, Беннетт признал самым вероятным описанием строки битов или набора данных самую короткую программу, способную их создать. (Если существует несколько программ, почти столь же коротких, как самая короткая, Беннетт также включил и их как приемлемые описания.) Затем Беннетт рассматривал вычислительную сложность этих коротких программ. Он назвал эту величину – усилия, необходимые для получения строки битов из ее самого вероятного описания, – логической глубиной.

Из всех мер сложности, которые исследовали мы с Хайнцем, логическая глубина оказалась самой привлекательной. Очевидно простые строки битов, например строка, состоящая из миллиарда единиц, могут быть созданы короткими и быстро выполняемыми программами («напечатать 1 один миллиард раз»), и они будут логически неглубокими. Случайные строки битов (например, 11010101100010… 011 – это строка битов, которую я создал лично, подбрасывая монетку и обозначив «орел» как 1, а «решку» как 0), можно создать с помощью длинных, но быстрых программ («напечатать 11010101100010… 011»), и они тоже логически неглубокие. А вот строку битов, соответствующую первому миллиону цифр числа p, даже посредством самых коротких известных программ придется считать долго, и эти строки логически глубоки. Логически глубокие строки битов обладают большим количеством структуры, и чтобы вычислить эту структуру с помощью самой короткой программы, нужно много времени.

Нам с Хайнцем очень нравились идеи Беннетта о сложности. Единственная жалоба Хайнца состояла в том, что эта схема недостаточно физическая. «Логическая глубина» относилась к строкам битов, компьютерным программам и логическим операциям. Хайнц хотел найти меру сложности, которая отсылала бы к физическим системам – энергии и энтропии. Поэтому мы с ним придумали физический аналог логической глубины, который назвали «термодинамической глубиной», чтобы подчеркнуть ее связь с работой Беннетта. Термодинамическая глубина – это свойство не битовых строк, а физических систем. Вместо поиска самого вероятного способа, которым строку битов можно было создать посредством самой короткой программы, мы с Хайнцем рассматривали самый вероятный способ создания физической системы. Наконец, вместо вычислительной сложности – количества логических операций, которые потребовались для создания данной строки битов, мы рассматривали объем физических ресурсов, необходимых для создания данной физической системы, скажем атома или слона.

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

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