007. Малый ШАД - Колмогоровская сложность, вероятность и энтропия - Алексей Сосинский

Понятие сложности конечной последовательности – последнее великое открытие Андрея Николаевича Колмогорова – дает точный математический ответ на вопрос, почему последовательность нулей и единиц 010010111001000101100011010101000111001010001101000111011000 нам кажется случайной (очень сложной), в то время как последовательность 010101010101010101010101010101010101010101010101010101010101 таковой не кажется – у нее сложность очень мала, она простая. В лекции будет дано определение сложности по Колмогорову. Для этого нам потребуется экскурс в теорию алгоритмов, в частности, будет введено понятие универсальной вычислимой функции – математической модели современного компьютера. Затем я расскажу о применениях сложности в теории информации, о ее связи с классической теорией вероятности и с термодинамикой. Если хватит времени, я упомяну о новейших и удивительных результатах исследований Ю.И.Манина и В.П.Маслова.