Древнегреческий исторический метод

"Эллины были искушенными людьми в практике судопроизводства, и грек без труда мог подвергнуть историческое свидетельство такой же критике, которую он привык применять по отношению к показаниям свидетелей в суде. Сочинения Геродота или Фукидида основываются большей частью на рассказах очевидцев, с которыми они лично контактировали. И их искусство исследователей заключалось в том, что они подвергали свидетеля свершившихся фактов перекрестному допросу до тех пор, пока в сознании последнего не вырисовывалась гораздо более полная и связная картина тех событий, чем та, которую он мог бы дать сам. В результате в сознании самого рассказчика впервые возникало подлинное знание тех событий, очевидцем которых он был, но о которых до сих пор у него было только doxa (мнение), а не episthmh (знание).

Этот подход греческого историка к сбору своих материалов весьма отличается от подхода современного историка, скажем, к использованию напечатанных мемуаров. Беспечная вера в соответствие первых воспоминаний о событии фактам сменяется в сознании очевидца очищенным, подвергнутым критике воспоминанием, воспоминанием, выдержавшим огонь таких вопросов, как: «А Вы совершенно уверены, что все помните именно так, как рассказываете?», «А Вы не противоречите ли тому, что заявляли вчера?», «Как Вы согласуете Ваш рассказ об этом событии с совершенно другим рассказом того-то и того-то?» Та необычайная основательность и связность повествований Геродота и Фукидида о Греции пятого века, несомненно, основывается именно на этом методе использования показаний очевидцев."

Читаю "Идею истории" Р. Дж. Коллингвуда. Это классический труд по философии истории -- то есть о истории как форме познания. Очень интересно. Жаль, что его не изучают в школе, а только, видимо, на исторических факультетах.

Случайность как незнание

При обсуждение поста "Случайность случайности", были справедливо подняты вопросы о связи случайности и сложности с криптографией. Я надеялся, что один из авторов прочитанной мною статьи даст коментарии, но вероятно он был слишком занят. Либо вопросы были слишком глупые. Тем не менее, a_shen написал, что у него с коллегами вышла недавно целая книга, посвещенная вопросам колмогровской сложности и алгоритмической случайности. Издана, кстати, книга отлично; у меня есть печатный вариант -- держать в руках одно удовольствие, а фрагменты рукописей Колмогорова на разворотах добавляют особого шарма. Так вот, в этой книге, вернее в первом "философском" приложении, есть некоторые рассуждения, имеющие прямое отношение к криптографии. Приведу небольшой фрагмент целиком.

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

Мы имеем в виду понятие генератора псевдослучайных битов (в смысле Блюма, Микэли и Яо; об этом центральном понятии современной сложностной криптографии можно прочесть, например, в книге Голдрайха [47]). Существование таких генераторов не доказано, но следует из некоторых сложностных предположений (существование односторонних функций), которые многие считают правдоподобными.

Объясним неформально, о чём идёт речь. Представим себе простую и быструю (полиномиальную) процедуру, которая берёт «зародыш» случайности (seed в англоязычной литературе), двоичное слово сравнительно небольшой длины, скажем, из тысячи битов. Эта процедура преобразует его в гораздо более длинное слово, скажем, в последовательность из 10^10 битов. Естественно, что получившееся слово имеет малую сложность, поскольку оно может быть задано указанием самой процедуры (которая проста по нашему предположению) и зародыша. Более того, даже и сложность с ограничением на время мала, поскольку преобразование предполагается легко вычислимым.

Тем не менее, если нам покажут такое слово из 10^10 битов, то мы можем и не отличить его от по-настоящему случайной последовательности. Это звучит па- радоксально: мы только что сказали, что колмогоровская сложность такого слова мала, а для случайных слов она близка к длине, в каком же смысле мы говорим о неотличимости?

Смысл этот вполне практический -- мы бы сразу согласились с тем, что это слово имеет малую сложность и потому нетипично, если бы нам показали зародыш. Но если нам дали это слово длины 10^10 просто так, то перебрать все 2^1000 возможных зародышей выше человеческих сил (даже если иметь в виду всё человечество со всеми его компьютерами), и никто так никогда и не узнает, что оно на самом деле было малой сложности.

Это соображение показывает, что в принципе мир может управляться простыми динамическими законами с достаточно простыми начальными условиями (описываемыми, скажем, тысячами битов). В таком мире «истинной» случайности не существует, и любая последовательность из 10^6 бросаний монеты (уже случившаяся, или которая случится в будущем) будет сильно сжимаемой. Тем не менее, вычислительно ограниченный наблюдатель (вроде нас самих) может никогда этого и не обнаружить.


Ссылка [47] -- это O. Goldreich -- Foundations of Cryptography, на русский, похоже, не переведена.