Add to ORKGAbstract. A computable presentation of the linearly ordered set (ω,≤), where ω is the set of natural numbers and ≤ is the natural order on ω, is any linearly ordered set L = (ω,≤L) isomorphic to (ω,≤) such that ≤L is a computable relation. Let X be subset of ω and XL be the image of X in the linear order L under the isomorphism between (ω,≤) and L. The degree spectrum of X is the set of all Turing degrees of XL as one runs over all computable presentations of (ω,≤). In this paper we study the degree spectra of subsets of ω. 1
AbstractA model is computable if its domain is a computable set and its relations and functions are ...
In computable model theory, mathematical structures are studied on the basis of their computability ...
© 2020, Pleiades Publishing, Ltd. Abstract: The investigation of computability in topological struct...
AbstractThe spectrum of a relation R on a computable structure is the set of Turing degrees of the i...
Let X be a unary relation on the domain of (ω,<). The degree spectrum of X on (ω,<) is the set of T...
We survey known results on spectra of structures and on spectra of relations on computable structure...
We prove that a nontrivial degree spectrum of the successor relation of either strongly η-like or no...
We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turi...
Linear orders and initial segments A linear order may be highly computable, but have complicated ini...
In this paper we construct linear orderings whoseΔ 2 0 -spectra coincide with classes of all high0 a...
A standard way to capture the inherent complexity of the isomorphism type of a countable structure i...
© 2018, Allerton Press, Inc. We give the collection of relations on computable linear orders. For an...
AbstractWe show that for every computably enumerable (c.e.) degree a>0 there is an intrinsically c.e...
We establish that for every computably enumerable (c.e.) Turing degree b, the upper cone of c.e. Tur...
AbstractA model is computable if its domain is a computable set and its relations and functions are ...
In computable model theory, mathematical structures are studied on the basis of their computability ...
© 2020, Pleiades Publishing, Ltd. Abstract: The investigation of computability in topological struct...
AbstractThe spectrum of a relation R on a computable structure is the set of Turing degrees of the i...
Let X be a unary relation on the domain of (ω,<). The degree spectrum of X on (ω,<) is the set of T...
We survey known results on spectra of structures and on spectra of relations on computable structure...
We prove that a nontrivial degree spectrum of the successor relation of either strongly η-like or no...
We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turi...
Linear orders and initial segments A linear order may be highly computable, but have complicated ini...
In this paper we construct linear orderings whoseΔ 2 0 -spectra coincide with classes of all high0 a...
A standard way to capture the inherent complexity of the isomorphism type of a countable structure i...
© 2018, Allerton Press, Inc. We give the collection of relations on computable linear orders. For an...
AbstractWe show that for every computably enumerable (c.e.) degree a>0 there is an intrinsically c.e...
We establish that for every computably enumerable (c.e.) Turing degree b, the upper cone of c.e. Tur...
AbstractA model is computable if its domain is a computable set and its relations and functions are ...
In computable model theory, mathematical structures are studied on the basis of their computability ...
© 2020, Pleiades Publishing, Ltd. Abstract: The investigation of computability in topological struct...