О строении частично упорядоченных множеств булевых степеней

На множестве всех бесконечных двоичных последовательностей рассматривается простейший вид алгоритмической сводимости – булева сводимость. Каждое множество $Q$ булевых функций, содержащее селекторную функцию и замкнутое относительно операции суперпозиции специального вида, порождает $Q$-сводимость и $Q$-степени – множества $Q$-эквивалентных последовательностей. $Q$-степень последовательности $\alpha$ характеризует относительную “информационную сложность” последовательности $\alpha$, при этом $Q$ является множеством операторов “извлечения” информации из бесконечных последовательностей. В работе изучаются частично упорядоченные множества $\mathcal L_Q$ всех $Q$-степеней для наиболее важных классов $Q$ булевых функций. Исследуется положение в $\mathcal L_Q$ периодических и узких $Q$-степеней, определяется число минимальных элементов и атомов, находятся начальные сегменты, изоморфные заданным конечным решеткам.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 03–01–00783.