колмогоров что такое равно

СОДЕРЖАНИЕ

Определение

Рассмотрим следующие две строки из 32 строчных букв и цифр:

Первая строка имеет короткое описание на английском языке, а именно » write ab 16 times «, которое состоит из 17 символов. У второго нет очевидного простого описания (с использованием того же набора символов), кроме записи самой строки, то есть » write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7 «, которая состоит из 38 символов. Следовательно, можно сказать, что операция записи первой строки имеет «меньшую сложность», чем запись второй.

Любая строка s имеет хотя бы одно описание. Например, вторая строка выше выводится программой:

тогда как первая строка выводится (гораздо более коротким) псевдокодом:

Длина самого короткого описания будет зависеть от выбора языка описания; но эффект изменения языков ограничен (результат, называемый теоремой инвариантности ).

Теорема инвариантности

Неформальное обращение

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

Вот пример оптимального языка описания. Описание будет состоять из двух частей:

Доказательство: любое описание D в L можно преобразовать в описание на оптимальном языке, сначала описав L как компьютерную программу P (часть 1), а затем используя исходное описание D в качестве входных данных для этой программы (часть 2). Общая длина этого нового описания D ′ составляет (приблизительно):

Более формальное обращение

Доказательство : в силу симметрии достаточно доказать, что существует некоторая константа c такая, что для всех строк s

Теперь предположим, что есть программа на языке L _1, которая действует как интерпретатор для L ₂ :

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

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

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

Есть несколько других вариантов колмогоровской сложности или алгоритмической информации. Наиболее широко используемый из них основан на программах с самоограничением и в основном принадлежит Леониду Левину (1974).

Аксиоматический подход к колмогоровской сложности, основанный на аксиомах Блюма (Blum 1967), был представлен Марком Бургином в статье, представленной для публикации Андреем Колмогоровым.

Основные результаты

Теорема : существует постоянная c такая, что

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

Наивная попытка программы для вычисления K

Формальное доказательство невычислимости K

Доказательство: в противном случае все бесконечное число возможных конечных строк могло бы быть сгенерировано конечным числом программ со сложностью ниже n бит.

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

который принимает на входе строку s и возвращает K ( s ). Все программы имеют конечную длину, поэтому для простоты доказательства предположим, что это 7 000 000 000 бит. Теперь рассмотрим следующую программу длины 1288 бит:

Используя KolmogorovComplexity в качестве подпрограммы, программа пробует каждую строку, начиная с самой короткой, пока не вернет строку с колмогоровской сложностью не менее 8 000 000 000 бит, то есть строка, которая не может быть создана какой-либо программой короче, чем 8 000 000 000 бит. Однако общая длина вышеуказанной программы, которая произвела s, составляет всего лишь 7 001 401 288 бит, противоречие. (Если код KolmogorovComplexity короче, противоречие остается. Если он длиннее, константу, используемую в, GenerateComplexString всегда можно изменить соответствующим образом.)

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

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

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

Сжатие

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

Теорема : существует константа L (которая зависит только от S и от выбора языка описания) такая, что не существует строки s, для которой утверждение

Мы можем найти эффективное перечисление всех формальных доказательств в S с помощью некоторой процедуры

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

При заданном n эта процедура пробует каждое доказательство, пока не найдет строку и доказательство в формальной системе S формулы K ( s ) ≥ L для некоторого L ≥ n ; если такого доказательства не существует, он зацикливается навсегда.

Наконец, рассмотрим программу, состоящую из всех этих определений процедур и главного вызова:

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

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

Принцип минимальной длины сообщения статистического и индуктивного вывода и машинного обучения был разработан К. С. Уоллесом и Д. М. Бултоном в 1968 году. MML является байесовским (то есть включает в себя предыдущие убеждения) и теоретико-информационным. Он имеет желаемые свойства статистической инвариантности (то есть логический вывод преобразуется с повторной параметризацией, например, из полярных координат в декартовы координаты), статистической согласованности (т.е. даже для очень сложных задач MML сходится к любой базовой модели) и эффективности ( т.е. модель MML будет сходиться к любой истинной базовой модели примерно так быстро, как это возможно). CS Wallace и DL Dowe (1999) показали формальную связь между MML и алгоритмической теорией информации (или сложностью Колмогорова).

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

Отношение к энтропии

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

Условные версии

Источник

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

Из Википедии — свободной энциклопедии

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

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

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

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

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

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

Источник

Колмогоровская сложность и наши поиски смысла

Что математика может рассказать нам о поиске порядка в хаосе жизни

Была ли встреча с самым дорогим вам человеком случайной, или виной тому была какая-то скрытая причина? А что насчёт странного вчерашнего сна – это были только случайные метания синапсов мозга, или он раскрыл что-то глубокое по поводу вашего подсознания? Возможно, сон пытался рассказать вам что-то о вашем будущем. Возможно, что и нет. Имеет ли тот факт, что ваш близкий родственник заболел опасной разновидностью рака, какой-то глубокий смысл, или же это просто последствия случайных мутаций ДНК?

В нашей жизни мы часто задумываемся над закономерностями происходящих вокруг нас событий. Мы задаёмся вопросом, случайны ли наши жизни, или у них есть какой-то смысл, уникально истинный и глубокий. Я, как математик, часто обращаюсь к числам и теоремам за идеями по поводу подобных вопросов. И так получилось, что я кое-что узнал о поиске смысла в закономерностях жизни благодаря одной из самых глубоких теорем математической логики. Эта теорема, проще говоря, демонстрирует, что в принципе невозможно узнать, является ли объяснение закономерности наиболее глубоким или интересным из всех объяснений. Точно так же, как в жизни, поиск смысла в математике ничем не ограничен.

Небольшая прелюдия. Рассмотрим следующие три строки символов.

2. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Как мы можем их описать? Например, мы легко можем это сделать, просто записав их – так, как мы только что и проделали. Однако сразу ясно, что первые две строчки можно описать и короче. Первая – это просто последовательность повторяющихся «100». Вторая – список первых нескольких простых чисел. А что насчёт третьей? Её можно описать, просто выведя всю строку. Но есть ли для неё лучшее, более короткое описание?

В начале 1960-х американский подросток Грегори Хайтин, всемирно известный русский [и советский] математик Андрей Николаевич Колмогоров, и пионер информатики Рэй Соломонов независимо друг от друга сформулировали способ измерения сложности последовательностей символов. Их идеи стали называть теорией сложности Колмогорова или алгоритмической теорией информации. Они постулируют, что сложность строки определяется длиной наикратчайшей компьютерной программы, способной её выдать. То есть, возьмём строчку, и поищем самую короткую компьютерную программу, которая её выдаёт. Программа – один из видов описания строки. Если кратчайшая из таких программ окажется очень короткой, тогда в строке есть простая закономерность, и она не очень сложная. Мы говорим, что в такой строке мало алгоритмическое содержание. И наоборот, если для выдачи строки требуется длинная программа, тогда строка сложная, и её алгоритмическое содержание больше. Для любой строки необходимо искать кратчайшую программу, выдающую такую строку. Длина такой программы называется Колмогоровской сложностью строки.

Давайте вернёмся к трём первым строчкам. Первые две строки можно описать при помощи относительно коротких компьютерных программ:

1. Вывести “100” 30 раз.

2. Вывести первые 25 простых чисел.

Колмогоровская сложность первой строки меньше Колмогоровской сложности второй строки, поскольку первая программа короче второй. Что насчёт третьей? У этой строчки нет очевидных закономерностей. Тем не менее, можно написать дурацкую программу, выводящую эту последовательность:

3. Вывести “38386274868783254735796801834682918987459817087106701409581980418”

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

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

Увы, такой компьютер создать невозможно! Пусть современные компьютеры и весьма мощны, эта задача невыполнима. Таково содержание одной из глубочайших теорем математической логики. Теорема, по сути, говорит, что Колмогоровскую сложность строки невозможно вычислить. Не существует механического устройства, определяющего размер наименьшей программы, выдающей заданную строку. Дело не в том, что наш текущий уровень компьютерных технологий не дотягивает до задачи, или что мы недостаточно умны для того, чтобы написать такой алгоритм. Было доказано, что сама идея описание и вычисления демонстрирует, что компьютер в принципе не в состоянии выполнить такую задачу для любой строки. И если компьютер, возможно, способен на поиски определённых закономерностей в строке, он не способен найти наилучшую закономерность. Мы, возможно, и найдём короткую программу, выводящую определённую последовательность, но всегда может существовать ещё более короткая. Мы никогда об этом не узнаем.

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

Парадокс интересных чисел связан с утверждением, что все натуральные числа интересные. 1 – это первое число, и это интересно. 2 – первое чётное число. 3 – первое нечётное простое число. 4 – интересное число, потому что 4 = 2 × 2 и 4 = 2+2. В таком роде можно продолжать дальше, и находить интересные свойства многих чисел. В какой-то момент мы можем встретить число без интересных свойств. И мы можем назвать это число первым неинтересным номером – но это само по себе уже интересное свойство. В итоге неинтересные числа тоже оказываются интересными!

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

Самое маленькое число, которое нельзя описать меньше, чем пятнадцатью словами [The smallest number that cannot be described in less than 15 words]

Для описания числа требуется 15, 16 или даже больше слов. Его нельзя описать 12, 13 или 14 словами. Однако, вот в чём проблема: приведённая выше фраза описывает это число при помощи 10 слов [по-английски – 12 слов / прим. перев.]. Наше описание числа противоречит описанию числа – вот вам и парадокс.

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

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

Много раз мы сталкивались с тем, что казалось нам совершенно хаотичным. Случайность нервирует нас, и мы ищем закономерности, частично устраняющие хаос. Если мы находим закономерность, остаётся неясным, является ли она лучшей закономерностью, объясняющей наши наблюдения. Мы можем задаться вопросом – существует ли более глубокая закономерность, дающая лучшее объяснение. Теория Колмогоровской сложности учит нас тому, что на базовом уровне не существует гарантированного способа определить наилучшую закономерность. Мы просто никогда не узнаем о том, является ли найденная нами закономерность наилучшей.

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

Реальный мир добавляет сложности. Если в мире строк и компьютерных программ ошибок нет, в реальном мире можно совершить ошибку. Мы легко узнаем, выводит ли какая-то определённая программа строку, или нет. И хотя мы, вероятно, не сможем определить оптимальную программу для вывода определённой строки, мы сможем определить, выводит ли она требуемую строку. А реальный мир, в отличие от этого, гораздо более сложный. Нам может показаться, что мы видим последовательность, когда её, на самом деле, нет.

Наше понимание наших поисков смысла начинает оформляться. Мы презираем случайности и обожаем закономерности. Мы биологически запрограммированы находить закономерности, объясняющие то, что мы видим. Но мы не можем быть уверены, что найденная нами закономерность будет правильной. Даже если бы мы каким-то образом могли гарантировать отсутствие ошибки, и достигли бы совершенства, подобного компьютерному, где-то всё равно всегда может находиться ещё более глубокая истина. Это напряжение подпитывает нашу любовь к литературе, театру и кино. Когда мы читаем роман или смотрим пьесу, автор или режиссёр представляет нам последовательность событий с общей темой, закономерностью или моралью. Литература, пьесы и кино предлагают нам великолепный способ убежать от обычно непонятного и бессмысленного хаоса, встречающегося нам в окружающем мире. Очень хорошая литература идёт дальше, и оставляет нам возможности многих интерпретаций. Мы лицом к лицу встречаемся с невычислимостью Колмогоровской сложности.

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

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

Нозон Яновски – доктор наук в математике, работает в Образовательном центре городского университета Нью-Йорка, профессор информатики в Бруклинском колледже того же университета.

Источник

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

Колмогоровскую сложность (англ. Kolmogorov complexity) можно рассматривать как способ измерения количества информации в строке.

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

Понятно, что эту строку можно описать более компактно на естественном языке, «128 нулей», всего 9 символов.

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

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

Содержание

Определения [ править ]

Декомпрессор [ править ]

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

Относительно каждого декомпрессора мы можем определить понятие сложности строки:

Примеры [ править ]

Свойства [ править ]

Тривиальные свойства [ править ]

Докажем последнее свойство:

Невычислимость [ править ]

Альтернативное доказательство с использованием теоремы о рекурсии [ править ]

Длина этой программы меньше длины минимальной программы, которая возвращает [math]x[/math] на пустом входе. Поэтому возникает противоречие. Следовательно [math] K [/math] невычислима.

Применение [ править ]

Альтернативное доказательство теоремы Гёделя о неполноте [ править ]

Г. Хайтин [1] заметил следующее:

Заметим, что во всех множествах пар все [math]n[/math] ограничены какой-то константой, следовательно существует огромное число истинных, но недоказуемых утверждений вида [math]KS(x) \geqslant n[/math]

Источник

Математика как образ жизни: теория вероятностей в судьбе Андрея Колмогорова

Иван Мин

Андрей Колмогоров — один из самых известных отечественных математиков, чей вес в науке сопоставим с Эвклидом, Эйлером или Ньютоном. 25 апреля ученому исполнилось бы 111 лет. В честь этого события в рамках проекта «Герой дня» состоялась лекция, посвященная Колмогорову. Ее прочитал поэт, писатель и математик Владимир Губайловский. Как стать великим в 40 лет, чем теория вероятностей обязана пуговицам, что связывает математику и поэзию — T&P публикуют конспект лекции.

План на 40 лет

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

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

Нужно понимать, в каких условиях 40-летний Колмогоров писал этот план. В этот момент он находился на даче в Комаровке. Вокруг шла война. 1943 год — победа еще не очевидна. Он же сидел и планировал следующие 40 лет своей жизни, намереваясь стать «великим человеком». А ведь к этому моменту Колмогоров уже был ученым с мировым именем. В этом проявляется и невероятная самоуверенность Колмогорова (он считает, что легко может стать великим), но и его необыкновенная скромность тоже, ведь все великие открытия, которые Колмогоров к тому моменту уже сделал, он считает недостаточными для того, чтобы стать великим человеком.

Детство гения

Мама Колмогорова, Мария Яковлевна, окончила курсы для школьных учителей и специализировалась как раз на математике. То есть для начала XX века она была женщиной довольно эмансипированной. Но Колмогоров ее совсем не знал, так как она умерла при его рождении. Андрея воспитывала тетя — Вера Яковлевна Колмогорова. Отец в воспитании сына участия не принимал. С раннего детства Колмогоров занимался математикой. В возрасте примерно 6 лет он заметил, что если складывать нечетные числа, то получаются точные квадраты. Это было первым самостоятельным открытием Колмогорова.

С тетей Верой Яковлевной, 1909 год

У себя дома Вера Яковлевна устроила небольшую школу, в которой она занималась с детьми, жившими по соседству. Под ее руководством издавался детский рукописный журнал «Весенние ласточки». Маленький Колмогоров отвечал в нем за математическую секцию. Он сам придумывал математические задачки. Одна из них — про пуговицу. Задача такая: есть пуговица с четырьмя дырками, чтобы пришить ее, достаточно сделать один стежок. Сколько есть разных способов пришить пуговицу? Эта задача уже связана с теорией множеств, которой Колмогоров будет много заниматься впоследствии.

Учеба

Колмогоров математике ни у кого и никогда не учился. Учителя просто не успевали его учить. Он выучился математике сам по «Энциклопедическому словарю Брокгауза и Ефрона». В своем дневнике он вспоминал: «Я решал трудные задачи, а в теории ушел много дальше школьных программ. Высшую математику изучал по статьям в энциклопедическом словаре Брокгауза и Ефрона, что не слишком легко, так как статьи эти имели не учебный характер, а, скорее, справочный». Когда Колмогоров поступил в Московский университет, он уже хорошо представлял себе университетский курс.

Первые годы в университете и мировая слава

В 1922 году Колмогоров поступил в университет. Он был настолько хорошо готов, что на сдачу экзаменов за первый курс ему понадобился всего месяц. Позднее он вспоминал: «Сдав в первые же месяцы экзамены за первый курс, я, как студент второго курса, получил право на 16 кг хлеба и 1 кг масла в месяц, что, по представлениям того времени, обозначало уже полное материальное благополучие. Одежда у меня была, а туфли на деревянной подошве я изготовил себе сам».

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

Андрей Колмогоров и А.М. Яглом, Комаровка, 1947 год

Сергей Петрович Капица однажды сказал: когда деды учат внуков — это беда, когда отцы учат детей — уже лучше, но самое лучшее — это когда старшие братья учат младших. Именно в такой ситуации и оказался Колмогоров в университете. Его учителя, математики Урысон и Александров, были старше его всего на 5–6 лет, поэтому их общение имело чрезвычайно плодотворный характер.Учеба Колмогорова в университете проходила в процессе совместной работы с более опытными коллегами. Это было непрерывное общение, постоянный обмен идей — только в таком смысле и учился Колмогоров математике.

Теория вероятностей

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

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

Колмогоров определил вероятность как меру. То есть мы можем измерять вероятность площадью. Если считать событием попадание капли в прямоугольники A, B, C, D, то как определить вероятность этого события? Попадет ли каждая конкретная капля в один из прямоугольников, зависит только от площади этих прямоугольников. Оказалось, что такой «площадной» подход отлично работает. Например: вероятность того, что капля попадет в прямоугольник A равна 0,3×0,4= 0,12, вероятность того, что она попадет в прямоугольник D — 0,6×0,7 = 0,42 и т.д.

Калькутта, Индия, 1962 год

Для теории вероятностей Колмогоров предложил свою аксиоматику. Третья аксиома гласит: вероятность всех событий равна 1 (то есть наша капля точно попадет в один из выделенных прямоугольников). Фундамент колмогоровской аксиоматики закладывает четвертая аксиома: если пересечение множеств A и B равно пустому множеству, то вероятность A, объединенного с B, равна сумме вероятностей A и B.

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

Ученики Колмогорова

Многих поражало, с какой легкостью Колмогоров ориентировался в самых разных областях математики и как моментально умел переключаться с одного предмета на другой. Колмогоров видел математику как некоторое целое и был одним из последних ученых, которым такое видение было доступно. Колмогоров уделял огромное внимание работе со своими учениками. Он выступал как своеобразный сеятель идей, которые разрабатывали в деталях уже его аспиранты. Сам же Колмогоров шел дальше. У него было два состояния окончания занятий проблемой: он или писал статью, или отдавал проблему своему ученику. А его ученики уже были готовы к тому, чтобы понять, что думает их учитель, загореться от него и решить проблему. Таким образом Колмогоров создал одну из крупнейших математических школ мира.

Стихи и математика

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

Колмогоров за составлением речи в Таллине, 1973 год

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

Теория сложности

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

Школа Колмогорова

Где-то к середине 1960-х годов знаменитая колмогоровская идейная продуктивность начала падать. Он продолжает занимать руководящие должности, но собственно науки в его жизни становится все меньше. В последний период Колмогоров всю свою энергию направил на педагогическую деятельность. И в этом прослеживается та же самая логика преемственности, которая красной нитью проходит через всю жизнь Колмогорова. Раньше он отдавал свои идеи коллегам и аспирантам, а теперь увлеченно занимается созданием математического интерната и разрабатывает и проводит реформу школьного математического образования (Колмогоров в соавторстве с другими учеными написал полный курс алгебры и полный курс геометрии для средней школы, и по этим учебникам в школах СССР велось преподавание). Реформа не всеми была встречена с одобрением, Колмогоров подвергся резкой критике как со стороны ученых, так и со стороны учителей. Но система специализированного физико-математического среднего образования, вдохновителем которой тоже выступил Колмогоров, оказалась очень удачной. Школа при университете (ныне СУНЦ имени Колмогорова), созданная Колмогоровым, до сих пор остается одной из лучших математических школ в России.

Источник

• ← Что такое драйвер?
• кошки в подвале многоквартирного дома что делать →