What Is a Random String?
Дата
Авторы
Calude,Cristian S.
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
Chaitin s algorithmic definition of random strings - based on the complexity induced by self-delimiting computers - is critically discussed. One shows that Chaitin s model satisfy many natural requirements related to randomness, so it can be considered as an adequate model for finite random objects. It is a better model than the original (Kolmogorov) proposal. Finally, some open problems will be discussed.
Ключевые слова
Blank-endmarker complexity , Chaitin (self-delimiting) complexity , random strings.