Вычислимость в иерархиях
Руководитель проекта: С.А.Бадаев
Исполнители проекта: З.Г.Хисамиев
Организация: НИИ мех. и мат. при КазНУ
Инвентарный номер: 0210РК01155
Регистрационный номер: 0109РК00793
Ключевые слова: Полурешетки Роджерса, Иерархия Ершова, Ершова иерархия, Вычислимости теория,
Область исследования: вычислимые нумерации семейств множеств иерархии Ершова и экспоненциальные классы сложности. Построены семейства разностей вычислимо перечислимых множеств с бесконечной слабо дистрибутивной полурешеткой Роджерса. Для каждого уровня иерархии Ершова доказано существование вычислимых семейств. Введены понятия слабой полноты (тривиальность и сильная тривиальность).