Geodesic
Relative Complexity for Computable Representations of the~Conventional Linear Order on the~Set of Naturals
Matematičeskie trudy, Tome 5 (2002) no. 1, pp. 114-128.

Voir la notice de l'article provenant de la source Math-Net.Ru

In the present article, we study the relationship between computable representations of the set of naturals with the conventional linear order. Two reducibility relations are introduced on the set of all such representations. Each of these relations determines a certain partially ordered set of degrees. We consider some questions concerning the algebraic structure of these posets and the interlocation of various degrees. 
@article{MT_2002_5_1_a7,
     author = {S. Yu. Podzorov},
     title = {Relative {Complexity} for {Computable} {Representations} of {the~Conventional} {Linear} {Order} on {the~Set} of {Naturals}},
     journal = {Matemati\v{c}eskie trudy},
     pages = {114--128},
     publisher = {mathdoc},
     volume = {5},
     number = {1},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MT_2002_5_1_a7/}
}
TY  - JOUR
AU  - S. Yu. Podzorov
TI  - Relative Complexity for Computable Representations of the~Conventional Linear Order on the~Set of Naturals
JO  - Matematičeskie trudy
PY  - 2002
SP  - 114
EP  - 128
VL  - 5
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MT_2002_5_1_a7/
LA  - ru
ID  - MT_2002_5_1_a7
ER  - 
%0 Journal Article
%A S. Yu. Podzorov
%T Relative Complexity for Computable Representations of the~Conventional Linear Order on the~Set of Naturals
%J Matematičeskie trudy
%D 2002
%P 114-128
%V 5
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MT_2002_5_1_a7/
%G ru
%F MT_2002_5_1_a7
S. Yu. Podzorov. Relative Complexity for Computable Representations of the~Conventional Linear Order on the~Set of Naturals. Matematičeskie trudy, Tome 5 (2002) no. 1, pp. 114-128. http://geodesic.mathdoc.fr/item/MT_2002_5_1_a7/

[1] Goncharov S. S., Ershov Yu. L., Konstruktivnye modeli, Nauchnaya kniga, Novosibirsk, 1999

[2] Dzgoev V. D., Goncharov S. S., “Avtoustoichivost modelei”, Algebra i logika, 19:1 (1980), 45–58 | MR | Zbl

[3] Rodzhers X., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972