Geodesic
Computable presentability of countable linear orders
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, Tome 158 (2018), pp. 81-115

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

The main goal of this paper is to study algorithmic properties of countable linear orders by constructing effective presentations of these structures on the set of natural numbers. In 1991, C. Jockusch and R. Soare constructed a low linear order without computable presentations. Before in 1989, R. Downey and M. Moses showed that each low discrete linear order has a computable copy. It is natural to ask for which order types of low presentations it is sufficient the existence of a computable presentation. This question (namely, research program) was stated by R. Downey in 1998: Describe the order property $P$ such that, for any low linear order $L$, $P(L)$ implies the existence of a computable presentation of $L$. In this paper, we give a detailed review of the main results in this direction. These results are mostly obtained by the author or in co-authorship.
Keywords: countable linear orders, computable structures, computable presentability, low degrees. 
@article{INTO_2018_158_a3,
     author = {A. N. Frolov},
     title = {Computable presentability of countable linear orders},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {81--115},
     publisher = {mathdoc},
     volume = {158},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2018_158_a3/}
}
TY  - JOUR
AU  - A. N. Frolov
TI  - Computable presentability of countable linear orders
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2018
SP  - 81
EP  - 115
VL  - 158
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2018_158_a3/
LA  - ru
ID  - INTO_2018_158_a3
ER  - 
%0 Journal Article
%A A. N. Frolov
%T Computable presentability of countable linear orders
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2018
%P 81-115
%V 158
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2018_158_a3/
%G ru
%F INTO_2018_158_a3
A. N. Frolov. Computable presentability of countable linear orders. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, Tome 158 (2018), pp. 81-115. http://geodesic.mathdoc.fr/item/INTO_2018_158_a3/