|
Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2017, Volume 159, Book 3, Pages 296–305
(Mi uzku1409)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Degree spectra of the block relation of $1$-computable linear orders
R. I. Bikmukhametov, M. S. Eryashkin, A. N. Frolov Kazan Federal University, Kazan, 420008 Russia
Abstract:
In this paper, we study the intrinsically computably enumerable relations on linear orderings, such as the successor relation on computable linear orderings and the block relation on $1$-computable linear orderings. For ease of reading, the linear ordering , in which the signature is enriched with the successor relation, is called $1$-computable linear ordering. This notion is consistent with the known results.
We have proved that for any $\mathbf0'$-computable linear ordering $L$ there exists a $1$-computable linear ordering, in which the degree spectrum of the block relation coincides with the $\Sigma_1^0$-spectrum of the linear ordering $L$. The degree spectrum of the block relation of a linear ordering $R$ is called the class of Turing degrees of the images of the block relation on computable presentations of $R$; and $\Sigma_1^0$-spectrum of a linear ordering $L$ is called the class of Turing enumerable degrees of $L$.
This obtained result provides a number of examples of the spectra of the block relation of $1$-computable linear orderings. In particular, the class of all enumerable high$_n$ degrees and the class of all enumerable non-low$_n$ degrees are realized by the spectra of the block relation of some $1$-computable linear orderings.
Keywords:
linear orders, $1$-computability, block relation, successivity relation, spectra of relations, intrinsically computably enumerable relations.
Received: 21.06.2017
Citation:
R. I. Bikmukhametov, M. S. Eryashkin, A. N. Frolov, “Degree spectra of the block relation of $1$-computable linear orders”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 159, no. 3, Kazan University, Kazan, 2017, 296–305
Linking options:
https://www.mathnet.ru/eng/uzku1409 https://www.mathnet.ru/eng/uzku/v159/i3/p296
|
Statistics & downloads: |
Abstract page: | 346 | Full-text PDF : | 148 | References: | 50 |
|