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