Answers are grounded in this paper and cite their sources.
We investigate the degree spectra of computable relations on canonically ordered natural numbers (ω ,<) ( ω , < ) and integers (ζ ,<) ( ζ , < ) . As for (ω ,<) ( ω , < ) , we provide several criteria that fix the degree spectrum of a computable relation to all c.e. or to all Δ ₂ Δ 2 degrees; this includes the complete characterization of the degree spectra of so-called computable block functions that have only finitely many types of blocks. Compared to Bazhenov et al. (in: LIPIcs, vol 219, pp 8:1–8:20, 2022), we obtain a more general solution to the problem regarding possible degree spectra on (ω ,<) ( ω , < ) , answering the question whether there are infinitely many such spectra. As for (ζ ,<) ( ζ , < ) , we prove the following dichotomy result: given an arbitrary computable relation R on (ζ ,<) ( ζ , < ) , its degree spectrum is either trivial or it contains all c.e. degrees. This result, and the proof techniques required to solve it, extend the analogous theorem for (ω ,<) ( ω , < ) obtained by Wright (Computability 7:349–365, 2018), and provide initial insight to Wright’s question whether such a dichotomy holds on computable ill-founded linear orders. This article is an extended version of Bazhenov et al. (in: LIPIcs, vol 219, pp 8:1–8:20, 2022).
No takes yet. Share an insight, caveat, or question.
Bazhenov et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: