|
Математическая логика, алгебра и теория чисел
Weak reducibility of computable and generalized computable numberings
Z. K. Ivanova, M. Kh. Faizrahmanov Kazan (Volga Region) Federal University, 18, Kremlyovskaya str., Kazan, 420008, Russia
Аннотация:
We consider universal and minimal computable numberings with respect to weak reducibility. A family of total functions that have a universal numbering and two non-weakly equivalent computable numberings is constructed. A sufficient condition for the non-existence of minimal $A$-computable numberings of families with respect to weak reducibility is found for every oracle $A$.
Ключевые слова:
computable numbering, $w$-reducibility, $A$-computable numbering, Rogers semilattice.
Поступила 28 января 2021 г., опубликована 12 мая 2021 г.
Образец цитирования:
Z. K. Ivanova, M. Kh. Faizrahmanov, “Weak reducibility of computable and generalized computable numberings”, Сиб. электрон. матем. изв., 18:1 (2021), 112–120
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1375 https://www.mathnet.ru/rus/semr/v18/i1/p112
|
Статистика просмотров: |
Страница аннотации: | 169 | PDF полного текста: | 152 | Список литературы: | 17 |
|