Email this article Turing Degrees in Refinements of the Arithmetical Hierarchy
- Authors: Selivanov V.L.1,2, Yamaleev M.M.2
-
Affiliations:
- Ershov Institute of Informatics Systems
- Kazan (Volga Region) Federal University
- Issue: Vol 57, No 3 (2018)
- Pages: 222-236
- Section: Article
- URL: https://journals.rcsi.science/0002-5232/article/view/234090
- DOI: https://doi.org/10.1007/s10469-018-9495-4
- ID: 234090
Cite item
Open Access
Access granted
Subscription Access
Abstract
We investigate the problem of characterizing proper levels of the fine hierarchy (up to Turing equivalence). It is known that the fine hierarchy exhausts arithmetical sets and contains as a small fragment finite levels of Ershov hierarchies (relativized to ∅n, n < ω), which are known to be proper. Our main result is finding a least new (i.e., distinct from the levels of the relativized Ershov hierarchies) proper level. We also show that not all new levels are proper.
About the authors
V. L. Selivanov
Ershov Institute of Informatics Systems; Kazan (Volga Region) Federal University
Author for correspondence.
Email: vseliv@iis.nsk.su
Russian Federation, pr. Akad. Lavrent’eva 6, Novosibirsk, 630090; ul. Kremlevskaya 18, Kazan, 420008
M. M. Yamaleev
Kazan (Volga Region) Federal University
Email: vseliv@iis.nsk.su
Russian Federation, ul. Kremlevskaya 18, Kazan, 420008
Supplementary files
