Generalized computable numberings and fixed points
Abstract
The paper proves that for any c.e. set W, its non-computability is equivalent to the fulfillment of the Recursion theorem (with parameters) in each universal W-computable numbering, as well as its weak precompleteness and nnonsplittability. It is established that the Turing completeness of the c.e. oracle W is equivalent to the existence of a precomplete W-computable numbering for any W-computable family.
About the Author
M. Kh. Faizrahmanov
Kazan Federal University, Volga Region Mathematical Center
Russian Federation
Russian Federation
18 Kremlyovskaya str., Kazan 420008
References
1. S. S. Goncharov, A. Sorbi, Generalized computable numerations and nontrivial rogers semilattices, Algebra and Logic 36 (6), 359–369 (1997). DOI: https://doi.org/10.1007/BF02671553
2. S. A. Badaev, S. S. Goncharov, The theory of numberings: open problems, Contemporary Math. 257, 23–38 (2000). URL: http://www.ams.org/books/conm/257/
3. S. A. Badaev, S. S. Goncharov, Rogers semilattices of families of arithmetic sets, Algebra and Logic 40 (5), 283–291 (2001). DOI: https://doi.org/10.1023/A:1012516217265
4. S. Y. Podzorov, Initial segments in Rogers semilattices of Σ0 n-computable numberings, Algebra and Logic 42 (2), 121–129 (2003). DOI: https://doi.org/10.1023/A:1023354407888
5. S. Y. Podzorov, Local structure of Rogers semilattices of Σ0 n-computable numberings, Algebra and Logic 44 (2), 82–94 (2005). DOI: https://doi.org/10.1007/s10469-005-0010-3
6. S. A. Badaev, S. S. Goncharov, Computability and numberings, in: S. B. Cooper (ed.) et al., New computational paradigms. Changing conceptions of what is computable, New York, NY, Springer-Verlag, 19–34 (2008).DOI: https://doi.org/10.1007/978-0-387-68546-5_2
7. M. Kh. Faizrakhmanov, Khutoretskii’s theorem for generalized computable families, Algebra and Logic 58 (4), 356–365 (2019). DOI: https://doi.org/10.1007/s10469-019-09557-9
8. S. A. Badaev, S. S. Goncharov, Generalized computable universal numberings, Algebra and Logic 53 (5), 355–364 (2014). DOI: https://doi.org/10.1007/s10469-014-9296-3
9. S. A. Badaev, I. I. Issakhov, Some absolute properties of A-computable numberings, Algebra and Logic 57 (4), 275–288 (2018). DOI: https://doi.org/10.1007/s10469-018-9499-0
10. M. Kh. Faizrahmanov, The Rogers semilattices of generalized computable enumerations, Sib. Math. J. 58 (6), 1104–1110 (2017). DOI: https://doi.org/10.1134/S0037446617060192
11. S. A. Badaev, S. S. Goncharov, A. Sorbi, Completeness and universality of arithmetical numberings, in: Computability and Models, Univ. Ser. Math., Kluwer/Plenum, New York, 11–44 (2003). DOI: https://doi.org/10.1007/978-1-4615-0755-0_2
12. S.Yu. Podzorov, On the limit property of the greatest element in the Rogers semilattice, Siberian Adv. Math. 15 (2), 104–114 (2005). URL: https://zbmath.org/?q=an:1095.03027
13. Y. L. Ershov, On inseparable pairs, Algebra and Logic 9 (6), 396–399 (1970). DOI: https://doi.org/10.1007/BF02219043
14. V. L. Selivanov, Precomplete numberings and functions without fixed points, Math. Notes 51 (1), 95–99 (1992). DOI: https://doi.org/10.1007/BF01229443
15. V. L. Selivanov, Precomplete numberings, J. Math. Sci. 256, 96–124 (2021). DOI: https://doi.org/10.1007/s10958-021-05422-2
16. H. Barendregt, S. A. Terwijn, Fixed point theorems for precomplete numberings, Ann. Pure App. Logic 170 (10), 1151–1161 (2019). DOI: https://doi.org/10.1016/j.apal.2019.04.013
17. Т. Н. Payne, Effective extandability and fixed points, Notre Dame J. Form. Log. 14 (1), 123–124 (1973). DOI: https://doi.org/10.1305/ndjfl/1093890819
18. S. A. Badaev, On weakly pre-complete positive equivalences, Sib. Math. J. 32 (2), 321–323 (1991). DOI: https://doi.org/10.1007/BF00972779
19. Yu. L. Ershov, Theory of numberings, Nauka, M., 1977 (in Russian).
20. Yu. L. Ershov, Theory of numberings, in: E.R. Griffor (ed.), Handbook of computability theory (Stud. Logic Found. Math., 140), Amsterdam, Elsevier, 473–503 (1999). DOI: https://doi.org/10.1016/S0049-237X(99)80030-5
21. R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in mathematical logic. Springer-Verlag, Berlin, Heidelberg, New York, etc., 1987. URL: https://link.springer.com/book/9783540666813
22. M. Kh. Faizrahmanov, Extremal numberings and fixed point theorems, Math. Log. Q. 68 (4), 398–408 (2022). DOI: https://doi.org/10.1002/malq.202200035
23. M. Kh. Faizrakhmanov, Universal generalized computable numberings and hyperimmunity, Algebra and Logic 56 (4), 337–347 (2017). DOI: https://doi.org/10.1007/s10469-017-9454-5
Review
For citations:
Faizrahmanov M.Kh. Generalized computable numberings and fixed points. Mathematics and Theoretical Computer Science. 2023;1(2):35-49. (In Russ.)
Views:
140
Email this article 