УДК 519.72

Построение последовательностей нулей и единиц со сложными конечными последовательностями / А. Ю. Румянцев. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2010. ? 1. С. 41-45.

Строятся бесконечные последовательности нулей и единиц, удовлетворяющие определенным ограничениям (не содержать подслов определенного вида или данных битов в данных позициях и т.п.). Рассматриваются вероятностные подходы к построению таких последовательностей с применением леммы Ловаса, а также их переформулировка на языке колмогоровской сложности и теории случайности по Мартин-Лефу.

Ключевые слова: колмогоровская сложность, префиксная сложность, последовательность, подпоследовательность, комбинаторика, вероятность.

Библиогр. 3.