RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2021, том 18, выпуск 1, страницы 112–120 (Mi semr1375)

Математическая логика, алгебра и теория чисел

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.

УДК: 510.5

MSC: 03D45

Поступила 28 января 2021 г., опубликована 12 мая 2021 г.

Язык публикации: английский

DOI: 10.33048/semi.2021.18.035



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


© МИАН, 2024