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