Универсальные центральные расширения конформных алгебр Ли // Вестн. <...> On free conformal and vertex algebras // J. <...> Conformal algebras // The Concise Handbook of Algebra. <...> Structure theory of finite conformal algebras // Selecta Math. <...> Поступила в редакцию 25.10.2008 УДК 519.72 ПОСТРОЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ НУЛЕЙ И ЕДИНИЦ СО СЛОЖНЫМИ КОНЕЧНЫМИ ПОСЛЕДОВАТЕЛЬНОСТЯМИ А.Ю. <...> Румянцев1 Строятся бесконечные последовательности нулей и единиц, удовлетворяющие определенным ограничениям (не содержать подслов определенного вида или данных битов в данных позициях и т.п.) <...> . Рассматриваются вероятностные подходы к построению таких последовательностей с применением леммы Ловаса, а также их переформулировка на языке колмогоровской сложности и теории случайности по Мартин-Лефу. <...> Вероятностный метод доказательства существования можно переформулировать так: берем случайную последовательность (в смысле алгоритмической теории вероятностей, т.е. определения Мартин-Лефа [1]) и проверяем, что она удовлетворяет всем ограничениям. <...> Связьслучайности по Мартин-Лефу и колмогоровской сложности демонстрирует теорема Левина– Шнорра. <...> Последовательность ω случайна по Мартин-Лефу тогда и только тогда, когда для некоторого c и для любого целого положительного числа n выполнено неравенство KP(ω([0,n))) n−c. <...> №1 Таким образом, префиксы случайной по Мартин-Лефу последовательности имеют большую сложнечного множества X ⊂ N верно неравенство KP(ω(X),X) |X|−O(1). <...> Здесь |X| обозначает число элементов в множестве X,а ω(X) — слово, составленное из битов последовательности ω с индексами в множестве X, записанных слева направо. <...> Если X =[0,n),то ω(X) определяет X, второй член пары не нужен и мы получаем теорему Левина–Шнорра в качестве частного случая. <...> Это утверждение дает критерий случайности, инвариантный относительно вычислимых перестановок последовательности. <...> Для данного c следует перечислитьсемейство интервалов, покрывающее T и имеющее меру не более 2−c. <...> Множество Tc задано как объединение интервалов (каждый интервал соответствует <...>