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