Laboratory of Mathematical Logic at PDMI

Пятница, 14 мая, комната 106. Начало в 18:00.

Докладчик: О. Сергеева.

Тема: О сложности по Колмогорову - "Do stronger definitions of randomness exist?".

Abstract

Доклад по статье Bruno Durand, Vladimir Kanovei, Vladimir. A. Uspensky, Nikolai Vereshchagin "Do stronger definitions of randomness exist?"

В первой части доклада будут кратко изложены основные определения и свойства колмогоровской сложности. В основном нас будет интересовать, каким образом к.с. позволяет определить и исследовать понятие случайности индивидуальной последовательности нулей и единиц. Но такое определение случайности отталкивается от понятия алгоритма, с которым теория вероятностей дела не имеет. Можно ли переформулировать "случайность" в терминах теории множеств? Цель, поставленная в статье: "Our goal will be to understand how far the notion of algorithm is necessary to define randomness and what kind of other definition can be or cannot be proposed".

Abstract статьи: In this paper we investigate refined definition of random sequences. Classical definitions (Martin-Lof tests of randomness, uncompressibility, unpredictability, or stochasticness) make use of the notion of algorithm. We present alternative definitions based on set theory and explain why they depend on the model of ZFC that is considered. We also present a possible generalisation of the definition when small infinite regularities are allowed.