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

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

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

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

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