Колмогоровская сложность

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

Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.

Выражает возможность фрактального описания.

К примеру, рассмотрим две строки длиной 64 символа, содержащие только символы в нижнем регистре и цифры:

abababababababababababababababababababababababababababababababab
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf

Первая строка имеет простое описание на естественном языке, а именно ab 32 раза, состоящее из 10 символов. Вторая строка не имеет очевидного простого описания с использованием того же набора символов, кроме собственно самой этой строки, длина которой составляет 64 символа.

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

Определение

Чтобы определить колмогоровскую сложность, мы должны сначала задать язык описания строк. Такой язык описания может быть основан на любом языке программирования, таком как Lisp, Pascal или Java. Если <math>P</math> — программа, выходом которой является строка <math>x</math>, то <math>P</math> — описание <math>x</math>. Длиной описания является длина <math>P</math> как строки. В ходе определения длины <math>P</math> длины подпрограмм, использующихся в <math>P</math>, должны быть вычислены. Длина любой целой константы <math>n</math>, которая появляется в <math>P</math>, это количество бит, требующихся для представления <math>n</math>, равное (грубо) <math>\log_2 n</math>.

Мы можем альтернативно выбрать кодировку для машины Тьюринга, где кодировка — функция, устанавливающая в соответствие каждой машине Тьюринга <math>M</math> битовую строку <math>\langle M\rangle</math>. Если <math>M</math> — машина Тьюринга, которая на вход <math>w</math> даёт на выходе строку <math>x</math>, то объединённая строка <math>\langle M\rangle w</math> есть описание для <math>x</math>. Это теоретический подход, который является более подходящим для построения детальных формальных доказательств и предпочтителен в исследовательской литературе. Двоичное лямбда-исчисление может дать наиболее простое определение сложности. В этой статье мы используем неформальный подход.

Любая строка <math>s</math> имеет как минимум одно описание, то есть программу

  function GenerateFixedString()
    return s

Если описание <math>s</math>, <math>d(s)</math> минимальной длины, то есть использует наименьшее количество символов, то оно называется минимальным описанием <math>s</math>, а длина <math>d(s)</math>, то есть количество символов в этом описании, — колмогоровской сложность <math>s</math>, <math>K(s)</math>. Символьно:

<math>K(s)=|d(s)|.</math>

Рассмотрим, как выбор языка описания влияет на значение <math>K</math> и покажем, что эффект от смены языка описания является ограниченным.

Теорема. Если <math>K_1</math> и <math>K_2</math> — функции сложности, относящиеся к языкам описания <math>L_1</math> и <math>L_2</math>, то существует константа <math>c</math> (зависящая только от языков <math>L_1</math> и <math>L_2</math>), такая, что

<math>\forall s|K_1(s)-K_2(s)|\leqslant c.</math>

Доказательство. Обратно, достаточно доказать, что существует некоторая константа <math>c</math>, такая, что для всех битовых строк <math>s</math>,

<math>K_1(s)\leqslant K_2(s)+c.</math>

Положим, что существует программа на языке <math>L_1</math>, которая работает как интерпретатор для <math>L_2</math>:

  function InterpretLanguage(string p)

где <math>p</math> — программа на языке <math>L_2</math>. Интерпретатор характеризуется следующим свойством:

Возвращаемым значением в результате работы InterpretLanguage на входных данных <math>p</math> будет результат работы <math>p</math>.

Таким образом, если <math>P</math> является программой на языке <math>L_2</math>, которая является минимальным описанием <math>s</math>, то InterpretLanguage(<math>P</math>) возвращает строку <math>s</math>. Длина этого описания <math>s</math> есть сумма:

1. Длины программы InterpretLanguage, которая может быть принята за константу <math>c</math>.
2. Длины <math>P</math>, определяемой <math>K_2(s)</math>.

Это доказывает искомую верхнюю оценку.

См. также: теорема инвариантности.

История и контекст

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

Идея теории колмогоровской сложности основана на ключевой теореме, впервые открытой Рэем Соломоноффом (англ. Ray Solomonoff), опубликовавшим её в 1960 году, описав в работе «A Preliminary Report on a General Theory of Inductive Inference» как часть своего изобретения алгоритмической вероятности. Он дал более полное описание в своих публикациях «A Formal Theory of Inductive Inference», часть 1 и 2 в журнале «Information and Control»., сделанных в 1964 году.

Позже А. Н. Колмогоров независимо опубликовал эту теорему в журнале «Проблемы передачи информации», Грегори Хайтин также представил эту теорему в журнале «J. ACM». Работа Хайтина была отправлена в октябре 1966, исправлена в декабре 1968 и цитирует обе работы Соломоноффа и Колмогорова.

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

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

Существуют некоторые другие варианты колмогоровской сложности или алгоритмической информации. Один из наиболее широко используемых основан на самоограниченных программах и в основном связывается с Л. А. Левиным (1974). Аксиоматических подход к колмогоровской сложности основа на аксиомах Блума (1967) был введен М. Бургиным (1982).

Некоторые полагают, что название «колмогоровская сложность» — это пример эффекта Матфея.

Основные следствия

В последующих рассуждениях под <math>K(s)</math> будем подразумевать сложность строки <math>s</math>.

Не сложно заметить, что минимальное описание строки не может быть больше, чем сама строка: приведённая выше программа GenerateFixedString, чей выход <math>s</math>, больше <math>s</math> на фиксированную величину.

Теорема. Существует константа <math>c</math>, такая, что

<math>\forall s\,K(s)\leqslant|s|+c.</math>

Невычислимость колмогоровской сложности

Первое следствие заключается в том, что нет эффективного способа вычисления <math>K</math>.

Теорема. <math>K</math> — невычислимая функция.

Другими словами, не существует программы, которая бы принимала на вход строку <math>s</math> и выдавала бы на выходе целое число <math>K(s)</math>. Покажем это с помощью противоречия путём создания программы, которая создает строку, создать которую возможно только более длинной программой. Предположим, что существует программа

  function KolmogorovComplexity(string s)

которая принимает на входе <math>s</math> и возвращает <math>K(s)</math>. Теперь рассмотрим программу

  function GenerateComplexString(int n)
     for i = 1 to infinity:
        for each string s of length exactly i
           if KolmogorovComplexity(s) >= n
              return s
              quit

Эта программа вызывает подпрограмму KolmogorovComplexity. Программа пробует каждую строку, начиная с кратчайшей, пока не найдет строку со сложностью как минимум <math>n</math>, которую возвращает. Следовательно, получив любое положительно целое число <math>n</math>, она производит строку с колмогоровской сложностью не меньше <math>n</math>. Эта программа имеет собственную фиксированную длину <math>U</math>. Входом программы GenerateComplexString является целое <math>n</math> и размер <math>n</math> измеряется количеством бит, необходимым для его представления, которое есть <math>\log_2 n</math>. Далее рассмотрим следующую программу:

  function GenerateParadoxicalString()
      return GenerateComplexString(n0)

Это программа вызывает GenerateComplexString как подпрограмму и также имеет свободный параметр <math>n_0</math>. Эта программа выводит строку <math>s</math>, чья сложность составляет как минимум <math>n_0</math>. При благоприятном выборе параметра <math>n_0</math> мы придём к противоречию. Чтобы выбрать это значение, заметим, что <math>s</math> описывается программой GenerateParadoxicalString, чья длина не больше, чем

<math>U+\log_2 n_0+C,</math>

где константа <math>C</math> добавлена из-за программы GenerateParadoxicalString. Так как <math>n</math> растёт быстрее, чем <math>\log_2 n</math>, существует значение <math>n_0</math>, такое, что

<math>U+\log_2 n_0+C<n_0.</math>

Но это противоречит определению о том, что имеется сложность как минимум <math>n_0</math>. То есть, по определению (<math>s</math>), допускается, что строка <math>s</math>, возвращаемая программой GenerateParadoxicalString, может быть создана программой длиной <math>n_0</math> или больше, но GenerateParadoxicalString короче, чем <math>n</math>₀. Так программа KolmogorovComplexity на самом деле не может вычислить сложность случайной строки.

Это доказательство от противного, где противоречие похоже на парадокс Берри: «Пусть <math>n</math> — наименьшее положительно целое, которое не может быть названо меньше чем двадцатью английскими словами.» Также возможно показать невычислимость <math>K</math> путём сведения невычислимости к задаче остановки <math>H</math>, так как <math>K</math> и <math>H</math> тьюринг-эквивалентны.

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

Цепное правило для колмогоровской сложности

Цепное правило для колмогоровской сложности утверждает, что

<math>K(X,\;Y)=K(X)+K(Y\mid X)+O(\log K(X,\;Y)).</math>

Оно утверждает, что кратчайшая программа, воспроизводящая <math>X</math> и <math>Y</math> не больше чем на <math>\log K(X,\;Y)</math> превосходит по размеру программу, воспроизводящую <math>X</math>, и программу, воспроизводящую <math>Y</math> при данном <math>X</math>. С использованием этого выражения можно определить аналог взаимной информации для колмогоровской сложности.

Сжатие

Вычислять верхнюю границу для <math>K(s)</math> несложно: нужно просто сжать строку <math>s</math> каким-либо методом, реализовать соответствующий декомпрессор на выбранном языке, соединить декомпрессор со сжатой строкой и измерить длину полученной строки.

Строка <math>s</math> сжимается на <math>c</math>, если имеет описание, длина которого не превосходит <math>|s|-c</math>. Это равнозначно утверждению <math>K(s)\leqslant|s|-c</math>. Если это не выполняется, то <math>s</math> не сжимается на <math>c</math>. Строка, не сжимаемая на 1, называется просто несжимаемой; по принципу Дирихле, несжимаемые строки должны существовать, так как есть <math>2^n</math> битовых строк длиной <math>n</math>, но только <math>2^n-1</math> строк длиной меньше <math>n</math>.

По той же причине, большинство строк сложны в том смысле, что они не могут быть значительно сжаты: <math>K(s)</math> не намного меньше <math>|s|</math>, длины <math>s</math> в битах. Чтобы уточнить, зафиксируем значение <math>n</math>. Существует <math>2^n</math> битовых строк длиной <math>n</math>. Равномерное распределение вероятностей на пространстве этих битовых строк определяется точно равным весовому коэффициенту <math>2^{-n}</math> для каждой строки длиной <math>n</math>.

Теорема. Вероятность того, что строка не сжимается на <math>c</math> равна как минимум <math>1-2^{-c+1}+2^{-n}</math> с равномерным распределением вероятностей на пространстве битовых строк длиной <math>n</math>.

Для доказательства этой теоремы заметим, что количество описаний длин не превосходит <math>n-c</math>, полученное из геометрической прогрессии:

<math>1+2+2^2+\ldots+2^{n-c}=2^{n-c+1}-1.</math>

Остается как минимум

<math>2^n-2^{n-c+1}+1</math>

битовых строк, несжимаемых на <math>c</math>. Для определения вероятности разделим на <math>2^n</math>.

Теорема Хайтина о неполноте

Нам известно, что во множестве всех возможных строк большинство строк являются сложными в том смысле, что не могут быть описаны в любом достаточно сжатом виде. Однако, оказывается, что тот факт, что конкретная строка сложна, не может быть формально доказан, если сложность строки выше определённого порога. Точная формализация представлена далее. Для начала зафиксируем частную аксиоматическую систему <math>\mathbf{s}</math> для натуральных чисел. Аксиоматическая система должна быть достаточно мощной, чтобы точному суждению <math>\mathbf{A}</math> о сложности строки можно было поставить в соответствие формулу <math>\mathbf{F}_\mathbf{A}</math> в аксиоматической системе <math>s</math>. Это соответствие должно обладать следующим свойством: если <math>\mathbf{F}_\mathbf{A}</math> выводится из аксиом <math>\mathbf{s}</math>, то соответствующее суждение <math>\mathbf{A}</math> истинно.

Теорема. Существует такая константа <math>L</math> (которая зависит только от частной аксиоматической системы и выбранного языка описания), что ни для одной строки утверждение

<math>K(s)\geqslant L</math>

не может быть доказано в рамках <math>\mathbf{s}</math>.

Тем не менее, как легко понять, утверждение <math>K(s)\geqslant L</math> будет истинным для бесконечного множества строк, а точнее, для всех строк, за исключением конечного их числа.

Доказательство теоремы основано на самореферентной конструкции, использованной в парадоксе Берри. Доказательство от противного. Если теорема не верна, то

Предположение (X): Для любого целого числа <math>n</math> существует строка <math>s</math>, для которой в <math>\mathbf{s}</math> существует вывод формулы «<math>K(s)\geqslant n</math>» (для которой мы предположили, что она может быть формализована в <math>\mathbf{s}</math>).

Рассмотрим программу, реализующую эффективное перечисление всех формальных доказательств в <math>\mathbf{s}</math>

  function NthProof(int n)

принимающую на вход n и выдающую некоторое доказательство. Некоторые из них доказывают формулу вида «<math>K(s)\geqslant n</math>», где s и n — константы в языке <math>\mathbf{s}</math>. Существует программа, проверяющая, доказывает ли n-ое доказательство формулу «<math>K(s)\geqslant L</math>»:

  function NthProofProvesComplexityFormula(int n)

Обратно, строка s и число L могут быть вычислены программами

  function StringNthProof(int n)

  function ComplexityLowerBoundNthProof(int n)

Рассмотрим теперь следующую программу:

  function GenerateProvablyComplexString(int n)
     for i = 1 to infinity:
        if  NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n
           return StringNthProof(i)

Принимая на вход n, эта программа проверяет каждое доказательство, пока не находит некоторую строку s и доказательство формулы K(s) ≥ L для некоторого L ≥ n. Эта программа останавливается по Предположению (X). Пусть эта программа имеет длину U. Существует число n₀, такое что U + log₂(n₀) + C < n₀, где C - дополнительная длина программы

  function GenerateProvablyParadoxicalString()
      return GenerateProvablyComplexString(n0)

Заметим, что число n₀ также закодировано в этой программе, на что требуется log₂(n₀) информации. Программа GenerateProvablyParadoxicalString выдает строку s, для которой существует L, такое что K(s) ≥ L может быть выведено в <math>\mathbf{s}</math>, причем L ≥ n₀. В частности для неё верно K(s) ≥ n₀. Однако s может быть описана программой длины U + log₂(n₀) + C, значит её сложность меньше n₀. Полученное противоречие доказывает ложность Предположения (X).

Подобные же идеи используются для доказательства свойств константы Хайтина.

Минимальная длина сообщения

Принцип минимальной длины сообщения в статистическом и индуктивном выводе и машинном обучении был разработан Уоллесом (англ. C. S. Wallace) и Болтоном (англ. D. M. Boulton) в 1968 году. Принцип МДС является байесовским (включает априорные вероятности) и информационно-теоретическим. Он обладает желаемыми свойствами статистической инвариантности (вывод трансформируется с репараметризацией), статистической связности (даже для очень трудной задачи принцип сойдется к нижележащей модели) и эффективности (модель, основанная на принципе МДС, сойдется к любой достоверной нижележащей модели так быстро, как это возможно). Уоллес и Доу (англ. D. L. Dowe) показали формальную связь между принципом МДС и алгоритмической теорией информации (или колмогоровской сложностью).

Колмогоровская случайность

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

Это определение можно расширить на бесконечные последовательности символов конечного алфавита. Определение можно изложить тремя эквивалентными способами. Первый способ использует эффективный аналог теории меры; другой использует эффективный мартингал. Третий способ определения таков: бесконечная последовательность случайна, если колмогоровская сложность её начального сегмента растет достаточно быстро — существует константа c, такая что сложность любого начального сегмента длины n не меньше n−c. Оказывается, что это определение, в отличие от определения случайности конечной строки, не зависит от выбора универсальной машины.

Связь с энтропией

Согласно теореме Брудно, энтропия динамической системы и алгоритмическая сложность траекторий в ней связаны соотношением <math>K(x;T) = h(T)</math> для почти всех <math>x</math>.

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

Литература

• Верещагин Н. К. [lpcs.math.msu.su/~ver/teaching/kolm-comp/index.html Курс колмогоровской сложности].
• Верещагин Н.К., Шень В.А. [www.mccme.ru/free-books/shen/kolmbook.pdf Колмогоровская сложность и алгоритмическая случайность]. — МЦНМО, 2013.
• Вьюгин В.В. [www.iitp.ru/upload/publications/5935/vyugin_kolm.pdf Колмогоровская сложность и алгоритмическая случайность].

Отрывок, характеризующий Колмогоровская сложность

В 6 м часу только у плотины Аугеста еще слышалась жаркая канонада одних французов, выстроивших многочисленные батареи на спуске Праценских высот и бивших по нашим отступающим войскам.
В арьергарде Дохтуров и другие, собирая батальоны, отстреливались от французской кавалерии, преследовавшей наших. Начинало смеркаться. На узкой плотине Аугеста, на которой столько лет мирно сиживал в колпаке старичок мельник с удочками, в то время как внук его, засучив рукава рубашки, перебирал в лейке серебряную трепещущую рыбу; на этой плотине, по которой столько лет мирно проезжали на своих парных возах, нагруженных пшеницей, в мохнатых шапках и синих куртках моравы и, запыленные мукой, с белыми возами уезжали по той же плотине, – на этой узкой плотине теперь между фурами и пушками, под лошадьми и между колес толпились обезображенные страхом смерти люди, давя друг друга, умирая, шагая через умирающих и убивая друг друга для того только, чтобы, пройдя несколько шагов, быть точно. так же убитыми.
Каждые десять секунд, нагнетая воздух, шлепало ядро или разрывалась граната в средине этой густой толпы, убивая и обрызгивая кровью тех, которые стояли близко. Долохов, раненый в руку, пешком с десятком солдат своей роты (он был уже офицер) и его полковой командир, верхом, представляли из себя остатки всего полка. Влекомые толпой, они втеснились во вход к плотине и, сжатые со всех сторон, остановились, потому что впереди упала лошадь под пушкой, и толпа вытаскивала ее. Одно ядро убило кого то сзади их, другое ударилось впереди и забрызгало кровью Долохова. Толпа отчаянно надвинулась, сжалась, тронулась несколько шагов и опять остановилась.
Пройти эти сто шагов, и, наверное, спасен; простоять еще две минуты, и погиб, наверное, думал каждый. Долохов, стоявший в середине толпы, рванулся к краю плотины, сбив с ног двух солдат, и сбежал на скользкий лед, покрывший пруд.
– Сворачивай, – закричал он, подпрыгивая по льду, который трещал под ним, – сворачивай! – кричал он на орудие. – Держит!…
Лед держал его, но гнулся и трещал, и очевидно было, что не только под орудием или толпой народа, но под ним одним он сейчас рухнется. На него смотрели и жались к берегу, не решаясь еще ступить на лед. Командир полка, стоявший верхом у въезда, поднял руку и раскрыл рот, обращаясь к Долохову. Вдруг одно из ядер так низко засвистело над толпой, что все нагнулись. Что то шлепнулось в мокрое, и генерал упал с лошадью в лужу крови. Никто не взглянул на генерала, не подумал поднять его.
– Пошел на лед! пошел по льду! Пошел! вороти! аль не слышишь! Пошел! – вдруг после ядра, попавшего в генерала, послышались бесчисленные голоса, сами не зная, что и зачем кричавшие.
Одно из задних орудий, вступавшее на плотину, своротило на лед. Толпы солдат с плотины стали сбегать на замерзший пруд. Под одним из передних солдат треснул лед, и одна нога ушла в воду; он хотел оправиться и провалился по пояс.
Ближайшие солдаты замялись, орудийный ездовой остановил свою лошадь, но сзади всё еще слышались крики: «Пошел на лед, что стал, пошел! пошел!» И крики ужаса послышались в толпе. Солдаты, окружавшие орудие, махали на лошадей и били их, чтобы они сворачивали и подвигались. Лошади тронулись с берега. Лед, державший пеших, рухнулся огромным куском, и человек сорок, бывших на льду, бросились кто вперед, кто назад, потопляя один другого.
Ядра всё так же равномерно свистели и шлепались на лед, в воду и чаще всего в толпу, покрывавшую плотину, пруды и берег.


На Праценской горе, на том самом месте, где он упал с древком знамени в руках, лежал князь Андрей Болконский, истекая кровью, и, сам не зная того, стонал тихим, жалостным и детским стоном.
К вечеру он перестал стонать и совершенно затих. Он не знал, как долго продолжалось его забытье. Вдруг он опять чувствовал себя живым и страдающим от жгучей и разрывающей что то боли в голове.
«Где оно, это высокое небо, которое я не знал до сих пор и увидал нынче?» было первою его мыслью. «И страдания этого я не знал также, – подумал он. – Да, я ничего, ничего не знал до сих пор. Но где я?»
Он стал прислушиваться и услыхал звуки приближающегося топота лошадей и звуки голосов, говоривших по французски. Он раскрыл глаза. Над ним было опять всё то же высокое небо с еще выше поднявшимися плывущими облаками, сквозь которые виднелась синеющая бесконечность. Он не поворачивал головы и не видал тех, которые, судя по звуку копыт и голосов, подъехали к нему и остановились.
Подъехавшие верховые были Наполеон, сопутствуемый двумя адъютантами. Бонапарте, объезжая поле сражения, отдавал последние приказания об усилении батарей стреляющих по плотине Аугеста и рассматривал убитых и раненых, оставшихся на поле сражения.
– De beaux hommes! [Красавцы!] – сказал Наполеон, глядя на убитого русского гренадера, который с уткнутым в землю лицом и почернелым затылком лежал на животе, откинув далеко одну уже закоченевшую руку.
– Les munitions des pieces de position sont epuisees, sire! [Батарейных зарядов больше нет, ваше величество!] – сказал в это время адъютант, приехавший с батарей, стрелявших по Аугесту.
– Faites avancer celles de la reserve, [Велите привезти из резервов,] – сказал Наполеон, и, отъехав несколько шагов, он остановился над князем Андреем, лежавшим навзничь с брошенным подле него древком знамени (знамя уже, как трофей, было взято французами).
– Voila une belle mort, [Вот прекрасная смерть,] – сказал Наполеон, глядя на Болконского.
Князь Андрей понял, что это было сказано о нем, и что говорит это Наполеон. Он слышал, как называли sire того, кто сказал эти слова. Но он слышал эти слова, как бы он слышал жужжание мухи. Он не только не интересовался ими, но он и не заметил, а тотчас же забыл их. Ему жгло голову; он чувствовал, что он исходит кровью, и он видел над собою далекое, высокое и вечное небо. Он знал, что это был Наполеон – его герой, но в эту минуту Наполеон казался ему столь маленьким, ничтожным человеком в сравнении с тем, что происходило теперь между его душой и этим высоким, бесконечным небом с бегущими по нем облаками. Ему было совершенно всё равно в эту минуту, кто бы ни стоял над ним, что бы ни говорил об нем; он рад был только тому, что остановились над ним люди, и желал только, чтоб эти люди помогли ему и возвратили бы его к жизни, которая казалась ему столь прекрасною, потому что он так иначе понимал ее теперь. Он собрал все свои силы, чтобы пошевелиться и произвести какой нибудь звук. Он слабо пошевелил ногою и произвел самого его разжалобивший, слабый, болезненный стон.
– А! он жив, – сказал Наполеон. – Поднять этого молодого человека, ce jeune homme, и свезти на перевязочный пункт!
Сказав это, Наполеон поехал дальше навстречу к маршалу Лану, который, сняв шляпу, улыбаясь и поздравляя с победой, подъезжал к императору.
Князь Андрей не помнил ничего дальше: он потерял сознание от страшной боли, которую причинили ему укладывание на носилки, толчки во время движения и сондирование раны на перевязочном пункте. Он очнулся уже только в конце дня, когда его, соединив с другими русскими ранеными и пленными офицерами, понесли в госпиталь. На этом передвижении он чувствовал себя несколько свежее и мог оглядываться и даже говорить.
Первые слова, которые он услыхал, когда очнулся, – были слова французского конвойного офицера, который поспешно говорил:
– Надо здесь остановиться: император сейчас проедет; ему доставит удовольствие видеть этих пленных господ.
– Нынче так много пленных, чуть не вся русская армия, что ему, вероятно, это наскучило, – сказал другой офицер.
– Ну, однако! Этот, говорят, командир всей гвардии императора Александра, – сказал первый, указывая на раненого русского офицера в белом кавалергардском мундире.
Болконский узнал князя Репнина, которого он встречал в петербургском свете. Рядом с ним стоял другой, 19 летний мальчик, тоже раненый кавалергардский офицер.
Бонапарте, подъехав галопом, остановил лошадь.
– Кто старший? – сказал он, увидав пленных.
Назвали полковника, князя Репнина.
– Вы командир кавалергардского полка императора Александра? – спросил Наполеон.
– Я командовал эскадроном, – отвечал Репнин.
– Ваш полк честно исполнил долг свой, – сказал Наполеон.
– Похвала великого полководца есть лучшая награда cолдату, – сказал Репнин.
– С удовольствием отдаю ее вам, – сказал Наполеон. – Кто этот молодой человек подле вас?
Князь Репнин назвал поручика Сухтелена.
Посмотрев на него, Наполеон сказал, улыбаясь:
– II est venu bien jeune se frotter a nous. [Молод же явился он состязаться с нами.]
– Молодость не мешает быть храбрым, – проговорил обрывающимся голосом Сухтелен.
– Прекрасный ответ, – сказал Наполеон. – Молодой человек, вы далеко пойдете!
Князь Андрей, для полноты трофея пленников выставленный также вперед, на глаза императору, не мог не привлечь его внимания. Наполеон, видимо, вспомнил, что он видел его на поле и, обращаясь к нему, употребил то самое наименование молодого человека – jeune homme, под которым Болконский в первый раз отразился в его памяти.
– Et vous, jeune homme? Ну, а вы, молодой человек? – обратился он к нему, – как вы себя чувствуете, mon brave?
Несмотря на то, что за пять минут перед этим князь Андрей мог сказать несколько слов солдатам, переносившим его, он теперь, прямо устремив свои глаза на Наполеона, молчал… Ему так ничтожны казались в эту минуту все интересы, занимавшие Наполеона, так мелочен казался ему сам герой его, с этим мелким тщеславием и радостью победы, в сравнении с тем высоким, справедливым и добрым небом, которое он видел и понял, – что он не мог отвечать ему.
Да и всё казалось так бесполезно и ничтожно в сравнении с тем строгим и величественным строем мысли, который вызывали в нем ослабление сил от истекшей крови, страдание и близкое ожидание смерти. Глядя в глаза Наполеону, князь Андрей думал о ничтожности величия, о ничтожности жизни, которой никто не мог понять значения, и о еще большем ничтожестве смерти, смысл которой никто не мог понять и объяснить из живущих.
Император, не дождавшись ответа, отвернулся и, отъезжая, обратился к одному из начальников:
– Пусть позаботятся об этих господах и свезут их в мой бивуак; пускай мой доктор Ларрей осмотрит их раны. До свидания, князь Репнин, – и он, тронув лошадь, галопом поехал дальше.
На лице его было сиянье самодовольства и счастия.
Солдаты, принесшие князя Андрея и снявшие с него попавшийся им золотой образок, навешенный на брата княжною Марьею, увидав ласковость, с которою обращался император с пленными, поспешили возвратить образок.
Князь Андрей не видал, кто и как надел его опять, но на груди его сверх мундира вдруг очутился образок на мелкой золотой цепочке.
«Хорошо бы это было, – подумал князь Андрей, взглянув на этот образок, который с таким чувством и благоговением навесила на него сестра, – хорошо бы это было, ежели бы всё было так ясно и просто, как оно кажется княжне Марье. Как хорошо бы было знать, где искать помощи в этой жизни и чего ждать после нее, там, за гробом! Как бы счастлив и спокоен я был, ежели бы мог сказать теперь: Господи, помилуй меня!… Но кому я скажу это! Или сила – неопределенная, непостижимая, к которой я не только не могу обращаться, но которой не могу выразить словами, – великое всё или ничего, – говорил он сам себе, – или это тот Бог, который вот здесь зашит, в этой ладонке, княжной Марьей? Ничего, ничего нет верного, кроме ничтожества всего того, что мне понятно, и величия чего то непонятного, но важнейшего!»
Носилки тронулись. При каждом толчке он опять чувствовал невыносимую боль; лихорадочное состояние усилилось, и он начинал бредить. Те мечтания об отце, жене, сестре и будущем сыне и нежность, которую он испытывал в ночь накануне сражения, фигура маленького, ничтожного Наполеона и над всем этим высокое небо, составляли главное основание его горячечных представлений.
Тихая жизнь и спокойное семейное счастие в Лысых Горах представлялись ему. Он уже наслаждался этим счастием, когда вдруг являлся маленький Напoлеон с своим безучастным, ограниченным и счастливым от несчастия других взглядом, и начинались сомнения, муки, и только небо обещало успокоение. К утру все мечтания смешались и слились в хаос и мрак беспамятства и забвения, которые гораздо вероятнее, по мнению самого Ларрея, доктора Наполеона, должны были разрешиться смертью, чем выздоровлением.
– C'est un sujet nerveux et bilieux, – сказал Ларрей, – il n'en rechappera pas. [Это человек нервный и желчный, он не выздоровеет.]
Князь Андрей, в числе других безнадежных раненых, был сдан на попечение жителей.


В начале 1806 года Николай Ростов вернулся в отпуск. Денисов ехал тоже домой в Воронеж, и Ростов уговорил его ехать с собой до Москвы и остановиться у них в доме. На предпоследней станции, встретив товарища, Денисов выпил с ним три бутылки вина и подъезжая к Москве, несмотря на ухабы дороги, не просыпался, лежа на дне перекладных саней, подле Ростова, который, по мере приближения к Москве, приходил все более и более в нетерпение.
«Скоро ли? Скоро ли? О, эти несносные улицы, лавки, калачи, фонари, извозчики!» думал Ростов, когда уже они записали свои отпуски на заставе и въехали в Москву.
– Денисов, приехали! Спит! – говорил он, всем телом подаваясь вперед, как будто он этим положением надеялся ускорить движение саней. Денисов не откликался.
– Вот он угол перекресток, где Захар извозчик стоит; вот он и Захар, и всё та же лошадь. Вот и лавочка, где пряники покупали. Скоро ли? Ну!
– К какому дому то? – спросил ямщик.
– Да вон на конце, к большому, как ты не видишь! Это наш дом, – говорил Ростов, – ведь это наш дом! Денисов! Денисов! Сейчас приедем.
Денисов поднял голову, откашлялся и ничего не ответил.
– Дмитрий, – обратился Ростов к лакею на облучке. – Ведь это у нас огонь?
– Так точно с и у папеньки в кабинете светится.
– Еще не ложились? А? как ты думаешь? Смотри же не забудь, тотчас достань мне новую венгерку, – прибавил Ростов, ощупывая новые усы. – Ну же пошел, – кричал он ямщику. – Да проснись же, Вася, – обращался он к Денисову, который опять опустил голову. – Да ну же, пошел, три целковых на водку, пошел! – закричал Ростов, когда уже сани были за три дома от подъезда. Ему казалось, что лошади не двигаются. Наконец сани взяли вправо к подъезду; над головой своей Ростов увидал знакомый карниз с отбитой штукатуркой, крыльцо, тротуарный столб. Он на ходу выскочил из саней и побежал в сени. Дом также стоял неподвижно, нерадушно, как будто ему дела не было до того, кто приехал в него. В сенях никого не было. «Боже мой! все ли благополучно?» подумал Ростов, с замиранием сердца останавливаясь на минуту и тотчас пускаясь бежать дальше по сеням и знакомым, покривившимся ступеням. Всё та же дверная ручка замка, за нечистоту которой сердилась графиня, также слабо отворялась. В передней горела одна сальная свеча.
Старик Михайла спал на ларе. Прокофий, выездной лакей, тот, который был так силен, что за задок поднимал карету, сидел и вязал из покромок лапти. Он взглянул на отворившуюся дверь, и равнодушное, сонное выражение его вдруг преобразилось в восторженно испуганное.
– Батюшки, светы! Граф молодой! – вскрикнул он, узнав молодого барина. – Что ж это? Голубчик мой! – И Прокофий, трясясь от волненья, бросился к двери в гостиную, вероятно для того, чтобы объявить, но видно опять раздумал, вернулся назад и припал к плечу молодого барина.
– Здоровы? – спросил Ростов, выдергивая у него свою руку.
– Слава Богу! Всё слава Богу! сейчас только покушали! Дай на себя посмотреть, ваше сиятельство!
– Всё совсем благополучно?
– Слава Богу, слава Богу!
Ростов, забыв совершенно о Денисове, не желая никому дать предупредить себя, скинул шубу и на цыпочках побежал в темную, большую залу. Всё то же, те же ломберные столы, та же люстра в чехле; но кто то уж видел молодого барина, и не успел он добежать до гостиной, как что то стремительно, как буря, вылетело из боковой двери и обняло и стало целовать его. Еще другое, третье такое же существо выскочило из другой, третьей двери; еще объятия, еще поцелуи, еще крики, слезы радости. Он не мог разобрать, где и кто папа, кто Наташа, кто Петя. Все кричали, говорили и целовали его в одно и то же время. Только матери не было в числе их – это он помнил.
– А я то, не знал… Николушка… друг мой!
– Вот он… наш то… Друг мой, Коля… Переменился! Нет свечей! Чаю!
– Да меня то поцелуй!
– Душенька… а меня то.
Соня, Наташа, Петя, Анна Михайловна, Вера, старый граф, обнимали его; и люди и горничные, наполнив комнаты, приговаривали и ахали.
Петя повис на его ногах. – А меня то! – кричал он. Наташа, после того, как она, пригнув его к себе, расцеловала всё его лицо, отскочила от него и держась за полу его венгерки, прыгала как коза всё на одном месте и пронзительно визжала.
Со всех сторон были блестящие слезами радости, любящие глаза, со всех сторон были губы, искавшие поцелуя.
Соня красная, как кумач, тоже держалась за его руку и вся сияла в блаженном взгляде, устремленном в его глаза, которых она ждала. Соне минуло уже 16 лет, и она была очень красива, особенно в эту минуту счастливого, восторженного оживления. Она смотрела на него, не спуская глаз, улыбаясь и задерживая дыхание. Он благодарно взглянул на нее; но всё еще ждал и искал кого то. Старая графиня еще не выходила. И вот послышались шаги в дверях. Шаги такие быстрые, что это не могли быть шаги его матери.
Но это была она в новом, незнакомом еще ему, сшитом без него платье. Все оставили его, и он побежал к ней. Когда они сошлись, она упала на его грудь рыдая. Она не могла поднять лица и только прижимала его к холодным снуркам его венгерки. Денисов, никем не замеченный, войдя в комнату, стоял тут же и, глядя на них, тер себе глаза.
– Василий Денисов, друг вашего сына, – сказал он, рекомендуясь графу, вопросительно смотревшему на него.
– Милости прошу. Знаю, знаю, – сказал граф, целуя и обнимая Денисова. – Николушка писал… Наташа, Вера, вот он Денисов.
Те же счастливые, восторженные лица обратились на мохнатую фигуру Денисова и окружили его.
– Голубчик, Денисов! – визгнула Наташа, не помнившая себя от восторга, подскочила к нему, обняла и поцеловала его. Все смутились поступком Наташи. Денисов тоже покраснел, но улыбнулся и взяв руку Наташи, поцеловал ее.
Денисова отвели в приготовленную для него комнату, а Ростовы все собрались в диванную около Николушки.
Старая графиня, не выпуская его руки, которую она всякую минуту целовала, сидела с ним рядом; остальные, столпившись вокруг них, ловили каждое его движенье, слово, взгляд, и не спускали с него восторженно влюбленных глаз. Брат и сестры спорили и перехватывали места друг у друга поближе к нему, и дрались за то, кому принести ему чай, платок, трубку.
Ростов был очень счастлив любовью, которую ему выказывали; но первая минута его встречи была так блаженна, что теперешнего его счастия ему казалось мало, и он всё ждал чего то еще, и еще, и еще.
На другое утро приезжие спали с дороги до 10 го часа.
В предшествующей комнате валялись сабли, сумки, ташки, раскрытые чемоданы, грязные сапоги. Вычищенные две пары со шпорами были только что поставлены у стенки. Слуги приносили умывальники, горячую воду для бритья и вычищенные платья. Пахло табаком и мужчинами.
– Гей, Г'ишка, т'убку! – крикнул хриплый голос Васьки Денисова. – Ростов, вставай!
Ростов, протирая слипавшиеся глаза, поднял спутанную голову с жаркой подушки.
– А что поздно? – Поздно, 10 й час, – отвечал Наташин голос, и в соседней комнате послышалось шуршанье крахмаленных платьев, шопот и смех девичьих голосов, и в чуть растворенную дверь мелькнуло что то голубое, ленты, черные волоса и веселые лица. Это была Наташа с Соней и Петей, которые пришли наведаться, не встал ли.
– Николенька, вставай! – опять послышался голос Наташи у двери.
– Сейчас!
В это время Петя, в первой комнате, увидав и схватив сабли, и испытывая тот восторг, который испытывают мальчики, при виде воинственного старшего брата, и забыв, что сестрам неприлично видеть раздетых мужчин, отворил дверь.
– Это твоя сабля? – кричал он. Девочки отскочили. Денисов с испуганными глазами спрятал свои мохнатые ноги в одеяло, оглядываясь за помощью на товарища. Дверь пропустила Петю и опять затворилась. За дверью послышался смех.