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

Что такое сложность?

Что такое сложность?

Вычислительная Вселенная спонтанно дает начало всем возможным формам вычисляемого поведения; все действия, которые можно запрограммировать, она программирует. Отчасти это поведение упорядоченное, отчасти случайное; иногда оно простое, иногда сложное. Но что такое сложность?

Я писал диссертацию по физике в Университете Рокфеллера, и однажды меня чуть не отчислили. Я поступил в Университет Рокфеллера потому, что он славится тем, что здесь поддерживают независимые исследования. Я сдал квалификационные экзамены и начал работу, связанную с ролью информации в квантово-механических системах и с тем, какое отношение квантовая обработка информации может иметь к фундаментальным процессам в физике, в том числе к квантовой гравитации. Иначе говоря, я занимался тем же самым, чем занимаюсь и сейчас, почти двадцать лет спустя. Научного руководителя у меня не было. И вот однажды (дело было в 1986 г.) в мой кабинет зашли два профессора и Хайнц Пэджелс, исполнительный директор Нью-Йоркской академии наук. «Ллойд, – сказали они, – вам следует прекратить работать над этой бредятиной и заняться темой, которую мы могли бы понять. В противном случае вам придется оставить Университет Рокфеллера».

Это заявление стало для меня полной неожиданностью. Я знал, что мои исследования выходят за рамки обычных тем кафедры. Почти все другие аспиранты работали над теорией струн – это очень абстрактная теория, которая вводит множество невидимых измерений в попытке согласовать квантовую теорию с общей теорией относительности и тем самым объяснить всю известную фундаментальную физику. Хоть убей, я не понимал, почему мои исследования более безумны, чем теория струн.

Но над теорией струн тогда работало много людей, а квантовой информацией в то время почти никто не занимался. Позже я познакомился с теми, кто это делал, и стал с ними сотрудничать, но тогда я даже не знал их имен. Немедленным результатом визита было то, что я сдался и согласился посвятить следующие несколько месяцев решению двух традиционных проблем квантовой теории поля. Но самым лучшим следствием угрозы вылететь из аспирантуры было то, что я стал сотрудничать с Хайнцем Пэджелсом. Хайнц был большой оригинал. Он носил двубортные костюмы в тонкую полоску и дорогую лакированную обувь. С зачесанными назад седыми волосами и в ботинках а-ля мафиози он напоминал Джона Готти, только более стройного. В физике он тоже был большим оригиналом… и вот он решил поруководить мною.

Через четыре месяца я разделался с обеими проблемами, которыми мне поручили заниматься «для порядка». Через восемь месяцев я убедил Хайнца, что рассмотреть испарение черных дыр с точки зрения квантовой обработки информации – не такая уж плохая идея. Через год он уже брал меня с собой в Ист-Виллидж, где мы встречались с его еще более эксцентричными друзьями – большинство из них были актерами. Он также представил меня своей жене, Элейн, автору «Гностических Евангелий» (Gnostic Gospels), книги, полностью изменившей мои взгляды на социальную природу религии. Возможно, мне все еще светило ремесло таксиста, как и очень многим другим безработным физикам со степенью, но теперь мне было хотя бы не скучно.

Поворотный пункт наших интеллектуальных отношений наступил в тот день, когда Хайнц зашел в мой кабинет и сказал:

– Ладно, Сет, но как мы будем измерять сложность?

– Так мы не можем этого сделать! – ответил я. – Вещи становятся сложными как раз тогда, когда числом это измерить невозможно.

– Ерунда, – сказал Хайнц, – давай попробуем.

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

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

В качестве меры сложности была также предложена алгоритмическая информация – кстати, Хайтин сначала назвал ее «алгоритмической сложностью». Но строки битов строки с высоким содержанием алгоритмической информации не выглядят сложными, они выглядят случайными; и действительно, алгоритмическую информацию также называют алгоритмической случайностью. Кроме того, строки битов с высоким содержанием алгоритмической информации легко создать: достаточно всего 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, даже посредством самых коротких известных программ придется считать долго, и эти строки логически глубоки. Логически глубокие строки битов обладают большим количеством структуры, и чтобы вычислить эту структуру с помощью самой короткой программы, нужно много времени.

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

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

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

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

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

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

Выводы предыдущей главы позволяют нам оценить логическую и термодинамическую глубину Вселенной в целом, а значит, найти верхнюю границу глубины всего, что она содержит. Общая сумма вычислительных усилий, потребовавшихся для создания Вселенной, составляет 10122 операций (логическая глубина), выполненных с 1092 битами (термодинамическая глубина).

Оглавление книги