|
Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2016, Number 6, Pages 15–26
(Mi ivm9119)
|
|
|
|
This article is cited in 4 scientific papers (total in 4 papers)
Initial segments of computable linear orders with computable natural relations
R. I. Bikmukhametov Kazan (Volga Region) Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia
Abstract:
We study the algorithmic complexity of natural relations on initial segments of computable linear orders. We prove that there exists a computable linear order with computable density relation such that its $\Pi^0_1$-initial segment has no computable presentation with computable density relation. We also prove that the same holds for right limit and left limit relations.
Keywords:
linear orders, initial segments, density relation, right limit relation, left limit relation.
Received: 17.10.2014 Revised: 19.01.2015
Citation:
R. I. Bikmukhametov, “Initial segments of computable linear orders with computable natural relations”, Izv. Vyssh. Uchebn. Zaved. Mat., 2016, no. 6, 15–26; Russian Math. (Iz. VUZ), 60:6 (2016), 12–20
Linking options:
https://www.mathnet.ru/eng/ivm9119 https://www.mathnet.ru/eng/ivm/y2016/i6/p15
|
|