RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2021 Volume 18, Issue 1, Pages 112–120 (Mi semr1375)

Mathematical logic, algebra and number theory

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

Abstract: 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$.

Keywords: computable numbering, $w$-reducibility, $A$-computable numbering, Rogers semilattice.

UDC: 510.5

MSC: 03D45

Received January 28, 2021, published May 12, 2021

Language: English

DOI: 10.33048/semi.2021.18.035



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024