RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1977, том 16, номер 2, страницы 129–148 (Mi al1554)

Эта публикация цитируется в 4 статьях

О вычислимых нумерациях семейств общерекурсивных функций

С. А. Бадаев


Аннотация: Все рассматриваемые нумерации предполагаются вычислимыми, $L(S)$ обозначает верхнюю полурешетку нумераций семейства $S$. Строится пример не эффективно дискретного семейства общерекурсивных функций, все нумерации которого попарно эквивалентны. Приводится необходимое и достаточное условие существования счётного числа попарно неэквивалентных однозначных нумераций семейства общерекурсивных функций $S$. В качестве следствий получается, что $L(S)$ содержит счётное число минимальных элементов в следующих случаях: 1) $S$ — дискретное семейство общерекурсивных функций и $L(S)$ содержит более одного элемента, 2) $S$ — семейство общерекурсивных функций, содержащее бесконечное вычислимое подсемейство предельных точек.

УДК: 517.11:518.5

Поступило: 20.10.1976



Реферативные базы данных:


© МИАН, 2024