|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
The Sum 2 KM(x)−K(x) Over All Prefixes x of Some Binary Sequence Can be Infiniteстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 19 декабря 2017 г.
- Авторы: Andreev Mikhail, Kumok Akim
- Журнал: Theory of Computing Systems
- Том: 58
- Номер: 3
- Год издания: 2016
- Издательство: Springer Verlag
- Местоположение издательства: Germany
- Первая страница: 424
- Последняя страница: 440
- DOI: 10.1007/s00224-014-9604-2
- Аннотация: We consider two quantities that measure complexity of binary strings: K M(x) is defined as the negative logarithm of continuous a priori probability on the binary tree, and K(x) denotes prefix complexity of a binary string x. In this paper we answer a question posed by Joseph Miller and prove that there exists an infinite binary sequence ω such that the sum of 2 K M(x)−K(x) over all prefixes x of ω is infinite. Such a sequence can be chosen among characteristic sequences of computably enumerable sets.
- Добавил в систему: Андреев Михаил Александрович