А. Н. Дегтев, М. Л. Платонов, “О $e$-главных нумерациях”, Сиб. матем. журн., 2008, том 49, номер 2,страницы 299

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

О $e$-главных нумерациях

А. Н. Дегтев, М. Л. Платонов

Тюменский государственный университет

Аннотация: Доказывается существование вычислимых семейств конечных множеств и общерекурсивных функций, не имеющих $e$-главных нумераций. Приводится серия примеров $e$-степеней, среди $p$-степеней вычислимых нумераций которых нет наибольшей.

Ключевые слова: частично рекурсивная функция, рекурсивно перечислимое множество, вычислимая нумерация, $e$-сводимость, $p$-сводимость.

УДК: 510.5

Статья поступила: 07.04.2003
Окончательный вариант: 09.08.2006