ФРИДБЕРГОВЫЕ НУМЕРАЦИИ С ГИПЕРИММУННЫМ ОРАКУЛОМ
Аннотация
Данная работа исследует некоторые вопросы, относящиеся к гипериммунности и Aвычислимым фридберговым нумерациям семейств всюду определенных функций. Было показано, что, если F является бесконечным A-вычислимым семейством всюду определенных функций, где A произвольное множество, то F имеет A-вычислимую фридбергову нумерацию; для любого гипериммунного множества A существует не рекурсивное вычислимое множество B; а также, если F является бесконечным A-вычислимым семейством всюду определенных функций, где A гипериммунное множество, то F имеет бесконечно много попарно не эквивалентные A-вычислимые фридберговы нумерации.
Об авторах
А. А. Исахов
АО «КБТУ»
Казахстан
Казахстан
доктор PhD, профессор
Ф. Рақымжанқызы
Казахский Национальный университет им. аль-Фараби
Казахстан
Казахстан
преподаватель
Список литературы
1. Rogers H. Godel numberings of partial computable functions J. Symbolic Logic, 1956, Vol. 23, pp. 49-57.
2. Soare R. I. Recursively enumerable sets and degrees. - Berlin; Heidelberg; New York: SpringerVerlag, 1987. - 437 p.
3. Miller W., Martin D. A. The degree of hyperimmune sets Z. Math. LogikGrundlag. Math., 1968, Vol. 14, pp. 159-166.
4. Ershov Yu. L. Theory of numberings Handbook of Computability Theory. - North-Holland; Amsterdam: Stud. Log. Found. Math., 1999, Vol. 140, pp. 473-503.
5. Badaev S. A., Goncharov S. S., Sorbi A. Completeness and universality of arithmetical numberings Computability and Models, S. B. Cooper and S. S. Goncharov (eds.). - New York: Kluwer Academic/Plenum Publishers, 2003, pp. 11-44.
6. Badaev S. A., Issakhov A. A. Some absolute properties of Л-computable numberings Algebra and Logic, 2018, Vol. 57, No. 4, pp. 275-288.
7. Issakhov A. A. Ideals without minimal elements in Rogers semilattices Algebra and Logic, 2015, Vol. 54, No. 3, pp. 197-203.
8. Issakhov A. A. A-computable numberings of the families of total functions The Bulletin of Symbolic Logic, 2016, Vol. 22, No. 3, p. 402.
9. Issakhov A. A., Rakymzhankyzy F. Hyperimmunity and A-computable numberings The Bulletin of Symbolic Logic, 2018, Vol. 24, No. 2, pp. 248-249.
Рецензия
Для цитирования:
Исахов А.А., Рақымжанқызы Ф. ФРИДБЕРГОВЫЕ НУМЕРАЦИИ С ГИПЕРИММУННЫМ ОРАКУЛОМ. Вестник Казахстанско-Британского технического университета. 2019;16(1):68-72.
For citation:
Issakhov A.A., Rakymzhankyzy F. FRIEDBERG NUMBERINGS WITH A HYPERIMMUNE ORACLE. Herald of the Kazakh-British technical university. 2019;16(1):68-72.
Просмотров:
305
Послать статью по эл. почте 