Глава 4 Информация и хаос

Глава 4

Информация и хаос

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

До этих пор законы, управлявшие газами, открывались эмпирически. Например, было известно, что давление газа в сосуде увеличивается с ростом температуры. Было также известно о соответствии между теплом и энергией: можно увеличить температуру жидкости, поставив ее на огонь или даже просто помешивая жидкость палочкой. Значит, тепло — это другая форма энергии.

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

* * *

ЦИКЛ КАРНО

Первая формулировка второго закона термодинамики принадлежит Николя Леонару Сади Карно (1796–1832) — французскому инженеру, который занимался изучением эффективности паровых машин. Карно сосредоточился на идеальной машине, или машине Карно, в которой источник тепла нагревает газ, газ расширяется и выполняет работу, чтобы затем снова сжаться при контакте с источником холода.

Карно открыл, что эффективность его машины ограничена разницей температур, создаваемых этими двумя источниками; он доказал также, что его идеальная машина — наиболее эффективная из возможных, но на практике любая машина будет менее эффективной. Это стало первой формулировкой второго принципа термодинамики, что в итоге привело к появлению понятия энтропии.

* * *

Однако в этих поисках родилось понятие энтропии. Физики того времени осознали, что в любом процессе во Вселенной энергия стремится распределиться таким образом, что всегда в итоге оказывается меньше полезной энергии, чем было вначале. Энтропия системы — это мера рассеивания ее энергии. Поскольку энергия стремится рассеиваться, как мы заметили в примере с двигателями, можно предположить, что энтропия в любом процессе стремится расти. Так родился второй закон термодинамикиf который гласит: суммарная энтропия изолированной системы будет увеличиваться.

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

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

Энтропия и вероятность

В предыдущей главе мы видели, что газ стремится к макросостоянию, для которого характерно наибольшее число микросостояний, совместимых с ним. Это дает нам много информации о макроскопическом состоянии газа. Предположим, что у системы есть три различных возможных макросостояния, из которых у первого — два микросостояния, совместимых с ним, у второго — четыре, а у третьего — 300 тысяч миллионов. Если мы наблюдаем систему в случайно выбранный момент, существует огромная вероятность того, что мы наблюдаем ее в третьем макросостоянии, просто потому что оно имеет намного больше возможностей для возникновения. Можно сказать, что вероятность третьего макросостояния намного больше, чем двух других.

Если мы посчитаем общее число микросостояний, получится:

N = 2 + 4 + 300 000 000 000 = 300 000 000 006.

Вероятность первого состояния равна числу микросостояний (2), разделенному на общее число возможных микросостояний, то есть:

Между тем вероятность третьего равна:

Позже мы увидим, как наиболее вероятные состояния соответствуют более высокой энтропии.

Теперь предположим, что у нас есть газ в коробке, и, используя поршень, мы заставляем все молекулы разместиться в ее верхнем углу, как показано на рисунке.

Если мы уберем поршень, как поведет себя газ? Куда будут двигаться его частицы?

Опыт и здравый смысл говорят нам, что они будут стремиться заполнить весь объем коробки. Это совпадает со вторым законом термодинамики, в котором утверждается, что энергия стремится от большей концентрации к меньшей. Вначале энергия очень концентрированная, поскольку она вся находится в углу коробки; но как только объем расширился, энергия стала меньше. Посмотрим, что гласит модель газа Больцмана.

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

Предположим, что наш газ имеет три частицы. В первом случае они будут ограничены верхней левой площадью коробки, отмеченной серым. Как видно, для этой области есть 25 возможных положений для каждой из частиц. Поскольку у нас есть три частицы, которые мы можем расположить где угодно без наложений, общее число микросостояний будет 25·24·23 = 13800.

Теперь обратим внимание на целую коробку. Ее сторона равна 10 единицам, так что общее число возможных позиций равно 100. Общее число микросостояний равно 100·99·98 = 970200. Итак, очевидно, что гораздо больше микросостояний совместимо со второй возможностью, чем с первой. Действительно, мы можем вычислить вероятность того, что газ окажется в верхнем углу. Это будет число совместимых микросостояний, разделенное на общее их число:

Итак, существует 98,6 % вероятности того, что газ займет всю коробку. Если бы мы взяли больше частиц и более мелкую сетку, то получили бы более значительную разницу. Таким образом, модель распределения Больцмана говорит то же самое, что и термодинамика.

Можно задаться вопросом, существует ли какой-нибудь микроскопический способ понять энтропию термодинамики. Энтропия — это величина, которая возрастает в каждом изолированном процессе и дает нам меру разрежения энергии. Можем ли мы найти какую-то величину, которая бы тоже выросла в процессе, который мы только что изучили? Ответ — да: возросло число микросостояний. Если в начале мы насчитывали их 13 800, то в конце — почти миллион. Число микросостояний показывает нам, какова вероятность получения этого макросостояния; кроме того, разумно предположить, что система всегда эволюционирует в сторону наиболее вероятного состояния. Итак, мы можем прийти к выводу, что энтропия и число микросостояний могут быть каким-то образом связаны.

* * *

ЛЮДВИГ БОЛЬЦМАН И АТОМЫ

Людвиг Больцман (1844–1906), портрет которого вы видите рядом с этими строками, был австрийским физиком, который ввел идею, что такие термодинамические явления, как температура, на самом деле — крупномасштабное проявление микроскопического поведения атомов. В то время само существование атомов еще вызывало дискуссии, и многие коллеги ученого отвергали его теорию, считая, что не существует никакого доказательства того, что материя состоит из элементарных частиц.

Больцман покончил жизнь самоубийством в 1906 году — как гласит легенда, из-за того, что научное сообщество отвергло его идеи. На самом деле это было связано с проблемами медицинского характера, а не с научным разочарованием. Через два года после смерти Больцмана Жан Батист Перрен (1870–1942) подтвердил существование атомов с помощью эксперимента над броуновским движением, в котором маленькие частицы пыли хаотично двигались, сталкиваясь с молекулами жидкости.

* * *

К этому же выводу пришел и Больцман, которому удалось доказать, что энтропия пропорциональна логарифму числа микросостояний, умноженному на его известную постоянную. Логарифм обозначается как log и является обратным экспоненте. Например, выражение log3 говорит нам, в какую степень мы должны возвести число 10, чтобы получить 3. Математически энтропия Больцмана выражается следующим образом:

S = k·logW,

где S — энтропия, k — постоянная Больцмана и W — число микросостояний.

Энтропия как хаос

В популярной литературе часто встречается объяснение энтропии как хаоса. Теперь, когда мы знаем связь между энтропией и числом микросостояний, мы можем понять, почему это происходит. Самый простой способ увидеть это — обратить внимание на доску, покрытую шашками.

Предположим, что мы ставим шашки в порядке, как показано на рисунке.

Каково сейчас число микросостояний, совместимых с этой конфигурацией? Чтобы найти его, воспользуемся рассуждениями из области комбинаторики, подобными приведенным в предыдущей главе. У нас 32 черные клетки и столько же белых. Мы ставим первую черную шашку на любое белое поле; для следующей есть только 31 вариант, и так далее. Следовательно, существует всего 32! способа распределить черные шашки, если считать, что они отличаются друг от друга. Точно так же есть 32! способа распределения белых шашек, так что всего у нас 32!·32! способов установить шашки, чтобы получить вышеуказанную конфигурацию.

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

Вычислим общую сумму возможных конфигураций всех шашек. Поскольку нам все равно, белая шашка или черная и где она находится, рассмотрим их все одновременно. Для первой у нас будет 64 возможности, для второй — 63, и так далее.

Итак, общее число конфигураций равно 64! Вероятность получения упорядоченной конфигурации равна числу упорядоченных конфигураций, разделенному на общее число конфигураций:

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

Энтропия как непредсказуемость

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

Можем пойти еще дальше и задать вопрос, какова минимально возможная энтропия для любой системы и какому количеству микросостояний она соответствует.

Вспомним, что энтропия равна:

S = k·logW,

где функция log — это логарифм, функция, обратная экспоненте. Предположим, что у нас только одно микросостояние: в этом случае логарифм единицы равен нулю, поскольку любое число, возведенное в нулевую степень, равно единице. Итак, энтропия одного микросостояния равна нулю. С точки зрения непредсказуемости это справедливо: нет более предсказуемой системы, чем та, у которой только одно состояние. Ее непредсказуемость точно равна нулю.

Энтропия как степень неосведомленности

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

Как было видно в предыдущей главе, обычно мы знаем давление, температуру и объем газа, но при этом не знаем всего остального, то есть мы обладаем смехотворным количеством информации, необходимой для описания состояния системы.

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

Какой же смысл в том, чтобы принимать энтропию за информацию? Информации нужен наблюдающий субъект — это не что-то, что можно потрогать. Когда мы говорим «энтропия системы — это степень нашей неосведомленности о ней», кажется, будто мы утверждаем, что энтропия не имеет реального существования во Вселенной, это просто человеческое понятие, которое измеряет то, что мы знаем, и не более.

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

Именно понимание энтропии как меры информации привело американского математика Клода Шеннона (1916–2001) к использованию ее в качестве ключевого элемента в своей теории информации.

Энтропия как информация

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

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

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

В нашу информационную эпоху все знают о том, что минимальной единицей информации является бит. Бит — это единица или ноль, аналог ответа на вопрос: «да» или «нет». Не существует меньшей единицы, ведь наименьшее, что мы можем передать, это присутствие или отсутствие чего-либо. Чтобы узнать содержание сообщения, мы должны перевести его в биты.

Посмотрим, как можно зашифровать фразу «Сегодня я опоздаю на ужин» в битах. При этом мы можем шифровать только два типа данных: ноль или один. Однако в двух битах мы можем зашифровать четыре: 00, 01,10, 11. В трех битах у нас уже восемь возможностей: 000, 001, 010, 011, 100, 101, 110, 111. А для n бит у нас есть 2ⁿ  возможностей, то есть два, умноженное на себя n раз. Каково минимальное число битов, нужное нам, чтобы зашифровать буквы алфавита? Поскольку в латинском алфавите 26 букв, нам потребуется по крайней мере 26 возможностей. Наиболее близкая степень двух — 32, или 23, так что минимальное необходимое число битов для того, чтобы зашифровать букву, равно пяти.

На практике для шифрования буквы используется более пяти битов, поскольку у нас есть заглавные буквы и различные символы, которые также нужно связать с последовательностью битов. Обычно используют восемь битов, из которых составлен так называемый код ASCII, который позволяет представить каждую букву в виде последовательности единиц и нулей. Например, буква а соответствует последовательности 01100001.

Коды ASCII для заглавных и строчных букв. Существует 8-битная кодировка кириллического алфавита, совместимая с ASCII, — КОИ-8.

Поскольку каждой букве соответствуют восемь битов, а наше сообщение содержит двадцать пять букв, мы можем сосчитать, сколько информации в нем содержится:

25·8 = 200 битов.

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

1111111111111111111111111111111111111111111111.

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

Энтропия Шеннона

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

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

Крайний случай — это цепочка, состоящая из единиц. Если мы знаем, что при броске всегда выпадает решка, то, подбрасывая монету, не получаем вообще никакой информации. Итак, когда цепочка битов полностью предсказуема, содержание информации в ней нулевое. Шеннон основывался на этой идее в сочетании с формулой энтропии Больцмана для создания собственного определения энтропии, применимого к информации.

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

Н = — P₁log₂P₁ — P₂log₂P₂ — P₃log₂P₃ — … — P_nlog₂P_n,

где H — энтропия, Р — вероятность получения некоторого значения для каждого символа.

Символы log₂ означают, что логарифм — это действие, обратное возведению в степень двух. Например, логарифм восьми по основанию два равен трем, поскольку три — это степень, в которую надо возвести два, чтобы получить восемь.

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

Формулу Шеннона можно использовать для определения информационной насыщенности сообщения, статистически исследовав появление в нем различных символов.

Возьмем предыдущий пример: «Сегодня я опоздаю на ужин». Порядок букв может показаться стихийным, и только зная, что фраза написана на русском языке, мы можем сделать какие-либо выводы о вероятности каждой буквы. Например, мы знаем, что в русском языке вероятность встретить букву ы после ж, ш или я после ч, щ крайне низка. Мы также знаем, что в начале слова никогда не встречаются буквы ъ и ь. Вся эта информация может использоваться для сжатия сообщения. Но даже если бы мы ничего не знали о языке как таковом, статистический анализ любого текста позволяет, основываясь на частоте каждой буквы, довольно сильно сжать его. Этот метод используется в программах для сжатия архивов: вначале они ищут в сообщении закономерности, а затем используют их для уплотнения информации.

Энтропия Шеннона измеряется в битах. Если вычислить ее содержание в букве такого текста, как эта книга, окажется, что она равна примерно одному биту, что намного меньше восьми битов, необходимых для передачи этой буквы.

* * *

ШЕННОН И ФОН НЕЙМАН

Определение энтропии Шеннона, кажется, гораздо больше связано с информацией, чем с энтропией, так что выбор названия может показаться удивительным. Согласно некоторым его биографам, идея принадлежала великому математику Джону фон Нейману (1903–1957), который во время одного из своих визитов сказал Шеннону следующее: «Тебе следует назвать ее энтропией по двум причинам. Во-первых, твоя функция неопределенности уже используется в статистической механике под таким названием, так что у нее уже есть имя. А во-торых, и это более важно, никто на самом деле не понимает, что такое энтропия, поэтому в спорах у тебя всегда будет преимущество».

* * *

Энтропия чисел

Поскольку число также может быть выражено как цепочка символов, в нем тоже имеется некоторое количество информации и, следовательно, некоторая энтропия Шеннона. Самый простой способ вычислить энтропию числа — это рассмотреть его выражение в двоичной системе. При этом вместо привычных арабских цифр используются единицы и нули. Когда мы записываем число арабскими цифрами, то на самом деле используем степени числа 10:

2345 = 2·1000 + 3·100 + 4·10 + 5·1 = 2·10³ + 3·10² + 4·10¹ + 5·10⁰.

Но мы можем использовать и степени числа два. Возьмем, например, число 10:

10 = 1·8 + 0·4 + 1·2 + 0·1 = 1·2³ + 0·2² + 1·2¹ + 0·2⁰.

Его запись в двоичной системе выглядит так:

1010.

Значит, для передачи числа 10 требуется четыре бита информации. В десятичной форме мы могли бы выразить 10 как:

10,000000000…

И для его передачи нам потребовалось бы бесконечное число символов. Двоичное выражение десяти также можно было бы представить в виде:

1010,000000000000000…

И снова нам потребовалось бы бесконечное количество битов для передачи его в таком виде. Однако, поскольку ноль после запятой повторяется бесконечно, он не несет никакой информации, и его энтропия Шеннона равна нулю. Итак, энтропия Шеннона числа 10 — четыре бита.

Теперь обратим внимание на хорошо всем нам известное число — ?. Это иррациональное число, то есть его десятичное выражение представляет собой бесконечный ряд цифр, следующих друг за другом без какой-либо регулярности. Невозможно сказать, какой будет следующая цифра числа ? на основе предыдущих, даже если их тысячи миллионов. Какова же энтропия Шеннона этого числа?

Десятичное представление К выглядит следующим образом:

3,14159265358979323846264338327950288419716939937510582097494459230781…

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

11,0010010000111111011010101000100010000101101000110000100011010011…

И снова мы сталкиваемся с бесконечным рядом непредсказуемых нулей и единиц. В соответствии с определением энтропии Шеннона, число ? содержит бесконечное количество информации, поскольку каждый его знак соответствует одному биту, и таких знаков бесконечное количество.

Многие математики предполагают, что, поскольку число знаков К бесконечно и они следуют в случайном порядке, должна существовать такая последовательность внутри числа ?, которая соответствовала бы полному содержанию «Одиссеи» в двоичном коде. Или должна быть последовательность, соответствующая двоичному представлению всех фотографий, которые читатель когда-либо сделал в своей жизни. Но подобные предположения пока остаются недоказанными.

Применение энтропии Шеннона

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

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

Поскольку любой физический или биологический процесс влечет за собой обмен и обработку информации, теория информации может применяться в изучении живых систем, например для определения плотности информации, содержащейся в молекуле ДНК. С этой точки зрения может быть проанализирован и человеческий мозг, поскольку этот орган в основном занимается обработкой информации. Последние оценки говорят о нашей способности обрабатывать примерно 50 битов в секунду. Подтверждает это и скорость нашего чтения: обычный человек читает около страницы в минуту. Если предположить, что на странице примерно триста слов, это составит около пяти слов в секунду, а если принять, что в слове 10 битов, окажется, что человек обрабатывает 50 битов в секунду.

Однако наши органы могут получить гораздо большее количество информации о внешнем мире. Так, глаза посылают в наш мозг около 10 млн битов в секунду. Но сырая информация, которую мы получаем, перед передачей в наши центры аналитической обработки должна быть очень сильно сжата.

Алгоритмическая теория информации

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

Этот альтернативный взгляд привел к появлению алгоритмической теории информации. Эта математическая теория, которая дополняет теорию Шеннона, была разработана сначала русским математиком Андреем Колмогоровым (1903–1987), а затем — аргентинско-американским математиком Грегори Хайтином (1947). Она основывается на понятии алгоритма — набора простых инструкций для компьютера. Ниже приведен пример алгоритма на вымышленном языке программирования, с помощью которого можно определить, является число символов во фразе четным или нечетным.

1. Посчитай число символов во фразе и сохрани результат в х.

2. Вычисли остаток деления х на два и сохрани результат в r.

3. Если r равен нулю, напиши на экране: «Число символов четное».

4. Если r не равен нулю, напиши на экране: «Число символов нечетное».

* * *

ГРЕГОРИ ХАЙТИН

Грегори Хайтин, родившийся в 1947 году, — аргентинско-американский программист и математик. Еще будучи подростком, он вывел алгоритмическую теорию информации и свою собственную версию теоремы Гёделя о неполноте, где показал, что количество недоказуемых теорем в математике намного больше, чем было принято считать. Сейчас Хайтин занимается метабиологией — математическим подходом к биологии, который изучает случайное развитие компьютерных программ для понимания биологической эволюции и возникновение творчества в строгой математической форме.

* * *

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

Существует программа, порождающая ее с помощью очень короткого кода.

1. Напиши единицу.

2. Вернись к началу программы.

В этой цепочке содержится очень мало информации.

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

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

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

Как видите, в этом конкретном случае алгоритмический подход несколько отличается от предложенного Шенноном, но в большинстве других случаев они согласуются. Например, для передачи случайной последовательности нулей и единиц самой короткой программе необходимо столько же бит, сколько цифр содержится в цепочке.

Число омега

Возникает вопрос: существует ли число, содержащее бесконечное количество информации по определению Колмогорова и Хайтина (подобное ? в определении Шеннона)? Да, такое число существует, и это одно из самых удивительных чисел в истории математики — число омега, известное также как постоянная Хайтина. Ее свойство заключается в том, что эта постоянная не может порождаться кодом, содержащим меньше битов, чем она сама. Это означает, что все биты числа омега полностью случайны.

Для того чтобы понять, что такое постоянная Хайтина, поговорим о проблеме остановки, которая заключается в том, чтобы определить, остановится ли какая-либо программа. Так, мы знаем, что программа, вычисляющая 2 + 2, остановится, как только будет найдена требуемая сумма. Но точно так же программа, вычисляющая все простые числа, не остановится никогда. Можно доказать, что способа решить проблему остановки для любой программы не существует: мы можем узнать, остановится ли какая-то конкретная программа, но не можем сделать этого для любого алгоритма.

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

Постоянную Хайтина можно понимать как вероятность того, что программа, выбранная наугад, остановится. Предположим, что во Вселенной существуют только программы, содержащие три бита информации, то есть всего таких программ восемь: 000, 001, 010, 011, 100, 101, 110, 111. Если бы останавливалась только программа 000, вероятность остановки составила бы 1/8.

Итак, мы можем вычислить вероятность того, что программа, выбранная наугад, остановится, если сложим вероятности выбора всех останавливающихся программ.

Результат будет равен единице, деленной на число программ, содержащих 2ⁿ битов.

Используем для обозначения суммы символ ?. Постоянная Хайтина в математической нотации записывается следующим образом:

Таким образом, число омега равно вероятности выбора случайной программы, которая остановится, и эта вероятность вычисляется суммированием вероятности выбора всех программ, которые останавливаются.

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

Число омега зависит от используемого языка программирования, так что, строго говоря, следует говорить о постоянных Хайтина — своей для каждого языка. Как мы видим, физическое понятие энтропии порождает математическую дисциплину, теорию информации, которая может быть использована при анализе самых разных ситуаций. Уточнение этого понятия ведет к открытиям, весьма далеким от области физики, но очень важным для чистой математики (например, в работах Хайтина). Впрочем, это обычный путь, которым идет математический прогресс.

* * *

ВЫЧИСЛЯЯ НЕВЫЧИСЛИМОЕ

Хотя постоянные Хайтина и невычислимы, в 2002 году математику Кристиану Калуду (родился в 1952 году) удалось вычислить первые шестьдесят четыре символа для одной из них. Используемый им способ заключался в том, чтобы взять все возможные программы с некоторым числом битов и выяснить, какие из них останавливаются. Вычислять знаки постоянной Хайтина — трудная задача, сложность которой растет с каждым новым знаком после запятой. Если бы в нашем распоряжении были хотя бы первые 10 тысяч битов постоянной Хайтина, мы бы находились на удивительном уровне развития математического знания. Хайтин даже утверждал, что количество знаков числа омега, известных цивилизации, — хорошая мера ее интеллектуального прогресса.

* * *

Энтропия, информация и черные дыры

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

Найти ответ на вопрос можно, рассмотрев микросостояния. Если у газа всего два возможных микросостояния, одного бита достаточно, чтобы определить, в каком из них он находится: ноль для первого, единица для второго. Но если у газа 100 тысяч микросостояний, количество информации равно наиболее близкой степени числа два, которая определяет число битов, необходимых для выбора одного из них.

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

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

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

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

Черная дыра — это область пространства, в которой материя так сжата, что даже свет не сможет высвободиться из нее, поскольку скорость освобождения выше скорости света. Скорость освобождения (или вторая космическая скорость) — это минимальная скорость, которую должно развить тело для того, чтобы преодолеть гравитационное притяжение планеты или звезды, на которой оно находится. Для Земли вторая космическая скорость равна примерно 11,2 км/с, но для черной дыры она так высока, что даже свет не достигает ее. Эйнштейн доказал, что ничто не может двигаться быстрее света, а это означает, что ничто не может освободиться из черной дыры.

Эйнштейн также в своей известной формуле Е = mс² показал, что масса и энергия — на самом деле одно и то же. Это означает, что огромная концентрация энергии соответствует огромной концентрации массы. Следовательно, можно создать черную дыру с помощью чистой энергии.

Итак, существует предел количества информации, которую можно хранить в какой-либо области пространства, и после превышения этого предела энергия хранения трансформируется в черную дыру. Как видите, максимальное количество информации содержат черные дыры.

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

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

Но это не так. Если кубики будут достаточно маленькими, то содержащаяся в них информация будет пропорциональна площади, которую они занимают, а не объему, как доказал Хокинг. Но это справедливо только в том случае, если кубики будут сжиматься в объеме, образовав в конце концов черную дыру — микроскопический объект, очень далекий от нашей повседневной действительности. Если плотность вещества меньше, чем в черной дыре, здравый смысл вновь будет демонстрировать свою эффективность.

Этот вывод Хокинга привел физическое сообщество к формулировке голографического принципа. Согласно ему, Вселенная представляет собой голограмму: кажется, что в ней три измерения, но на самом деле вся необходимая информация находится на плоскости. Знакомая нам трехмерная Вселенная не более чем иллюзия — на самом деле в ней на одно измерение меньше.

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

Как видите, физическое понятие снова нашло применение в математике, оно там было отшлифовано, расширено и вновь возвращено в лоно физики, чтобы стать основой революционных открытий в нашем понимании Вселенной.

Гравитация как энтропия

Понятие энтропии нашло также неожиданное применение в теории энтропической гравитации Эрика Верлинде (1962), согласно которой предполагается, что гравитации не существует, она — всего лишь эффект энтропии в комбинации с голографическим принципом.

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

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

Теория Верлинде объясняет некоторые свойства гравитации различием в плотности энтропии в пространстве между двумя телами и в окружающем пространстве.

Как говорит ученый, «законы Ньютона не работают на микроуровне, но они действуют на уровне яблок и планет. Вы можете сравнить это с давлением газа. Сами по себе молекулы газа не создают никакого давления, но некоторый объем газа оказывает давление».

Сегодня теория Верлинде все еще находится на уровне гипотез и ждет подтверждения физическим сообществом.

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