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

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

M. Kh. Faizrahmanov
Minimal generalized computable enumerations and high degrees

We establish that the set of minimal generalized computable enumerations of every infinite family computable with respect to a high oracle is effectively infinite. We find some sufficient condition for enumerations of the infinite families computable with respect to high oracles under which there exist minimal generalized computable enumerations that are irreducible to the enumerations.

DOI 10.17377/smzh.2017.58.318
Ключевые слова: обобщенно вычислимая нумерация, минимальная нумерация, высокое множество, 2-низкое множество, арифметическая нумерация.

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

• PDF file
• PostScript file