Relations between varieties of Kolmogorov complexities

Uspensky, V.A.; Shen, A.

Авторы: Uspensky V.A., Shen A.
Журнал: Mathematical Systems Theory
Том: 29
Номер: 3
Год издания: 1996
Первая страница: 271
Последняя страница: 292
DOI: 10.1007/BF01201280
Аннотация: There are several sorts of Kolmogorov complexity, better to say several Kolmogorov complexities: decision complexity, simple complexity, prefix complexity, monotone complexity, a priori complexity. The last three can and the first two cannot be used for defining randomness of an infinite binary sequence. All those five versions of Kolmogorov complexity were considered, from a unified point of view, in a paper by the first author which appeared in Watanabe's book [23]. Upper and lower bounds for those complexities and also for their differences were announced in that paper without proofs. (Some of those bounds are mentioned in Section 4.4.5 of [16].) The purpose of this paper (which can be read independently of [23]) is to give proofs for the bounds from [23]. The terminology used in this paper is somehow nonstandard: we call “Kolmogorov entropy” what is usually called “Kolmogorov complexity.” This is a Moscow tradition suggested by Kolmogorov himself. By this tradition the term “complexity” relates toany mode of description and “entropy” is the complexity related to anoptimal mode (i.e., to a mode that, roughly speaking, gives theshortest descriptions).
Добавил в систему: Успенский Владимир Андреевич

	ИСТИНА	Войти в систему Регистрация
	ИПМех РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИПМех РАН

Relations between varieties of Kolmogorov complexitiesстатья

Прикрепленные файлы