УДК 519.72
Построение последовательностей нулей и единиц со сложными конечными последовательностями / А. Ю. Румянцев // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2010. ? 1. С. 41-45.
Строятся бесконечные последовательности нулей и единиц, удовлетворяющие определенным ограничениям (не содержать подслов определенного вида или данных битов в данных позициях и т. п.). Рассматриваются вероятностные подходы к построению таких последовательностей с применением леммы Ловаса, а также их переформулировка на языке колмогоровской сложности и теории случайности по Мартин-Лефу.
Ключевые слова: колмогоровская сложность, префиксная сложность, последовательность, подпоследовательность, комбинаторика, вероятность.
Библиогр. 3.
