Еженедельный семинар Лаборатории

Семинар состоится в пятницу 22 ноября в 17.00 в аудитории 1001. На семинаре выступит Александр Шень (CNRS) с докладом "Как измерить случайность индивидуальной последовательности?".

Аннотация: Классическая теория вероятностей рассматривает вероятностные меры, скажем, равномерную (бернуллиеву) меру на последовательностях нулей и единиц, в которой все биты независимы и равновероятны. Однако с точки зрения чистой теории меры последовательность 00000... ничуть не хуже, чем любая другая последовательность – существует сохраняющий меру автоморфизм, переводящий первую во вторую. Можно ли как-то объяснить, в каком смысле последовательность 00000... (или, скажем, двоичное разложение числа \pi) "не случайна"? В своё время такой подход, использующий теорию алгоритмов, был предложен Мартин-Лёфом. Я расскажу о некотором варианте этого подхода, связанном с дефектами случайности относительно меры или класса мер: мы увидим, что некоторые теоремы классической теории меры могут быть сформулированы на этом языке.

Предварительных знаний из теории алгоритмов (выходящих за общечеловеческие представления об исполнении программ компьютерами) не предполагается.