Файзрахманов М. Х.
О полурешетках Роджерса обобщенно вычислимых нумераций

Исследуются мощностные и структурные свойства полурешеток Роджерса обобщенно вычислимых нумераций относительно произвольных невычислимых оракулов и оракулов, имеющих гипериммунные тьюринговы степени. Установлено, что полурешетка Роджерса обобщенно вычислимых относительно невычислимого оракула нумераций любого нетривиального семейства бесконечна. Для случая оракулов гипериммунной степени доказано, что полурешетка Роджерса любого бесконечного семейства содержит идеал без минимальных элементов, а также установлена предельность наибольшего элемента в случае его наличия при условии, что семейство содержит наименьшее по включению множество.

M. Kh. Faizrahmanov
The Rogers Semilattices of Generalized Computable Enumerations

We study the cardinality and structural properties of the Rogers semilattice of generalized computable enumerations with arbitrary noncomputable oracles and oracles of hyperimmune Turing degree. We show the infinity of the Rogers semilattice of generalized computable enumerations of an arbitrary nontrivial family with a noncomputable oracle. In the case of oracles of hyperimmune degree we prove that the Rogers semilattice of an arbitrary infinite family includes an ideal without minimal elements and establish that the top, if present, is a limit element under the condition that the family contains the inclusion-least set.

DOI 10.17377/smzh.2017.58.619
Ключевые слова: вычислимая нумерация, обобщенно вычислимая нумерация, полурешетка Роджерса, гипериммунное множество, минимальная нумерация, универсальная нумерация.

Полный текст статьи / Full texts:

• PDF file