Вычислимые семейства конечнозначных общерекурсивных функций
| Авторы: | Ю. Д. Корольков |
| Аннотация: | Доказана представимость индексных множеств всех вычислимых семейств общерекурсивных функций индексными множествами вычислимых семейств конечнозначных неубывающих общерекурсивных функций. |
| Ключевые слова: | индексное множество, общерекурсивная функция |
| УДК: | 518.5 |
| Литература: |
1. Ершов Ю. Л. Теория нумераций / Ю. Л. Ершов. – М.: Наука, 1977. 2. Корольков Ю.Д. Оценка сложности индексных множеств семейств общерекурсивных функций в арифметической иерархии / Ю. Д. Корольков // Алгебра и логика. – 2002. – Т. 41, № 2. – С. 155–165. 3. Селиванов В. Л. Тонкие иерархии арифметических множеств и определимые индексные множества / В. Л. Селиванов // Математическая логика и алгоритмические вопросы. – 1989. – Т. 12. – С. 165–185. 4. Ershov Yu. L. Theory of numberings / Yu. L. Ershov // Preprint 18. – Novosibirsk, 1996. |