Статья
2016
Universal computable enumerations of finite classes of families of total functions
M. Kh. Faizrakhmanov
Русская математика
https://doi.org/10.3103/S1066369X16120112
Abstract / Full Text
In the paper we introduce the notion of a computable enumeration of a class of families. We prove a criteria for the existence of universal computable enumerations of finite classes of computable families of total functions. In particular, we show that there is a finite computable class of families of total functions without universal computable enumerations.
Author information
- Kazan (Volga Region) Federal University, ul. Kremlyovskaya 18, Kazan, 420008, RussiaM. Kh. Faizrakhmanov
References
- Goncharov, S. S. and Sorbi, A. “Generalized Computable Numerations and Nontrivial Rogers Semilattices”, Algebra and Logic 36, No. 6, 359–369 (1997).
- Podzorov, S. Yu. “Initial Segments in Rogers Semilattices of Σ 0n -Computable Numberings”, Algebra and Logic 42, No. 2, 121–129 (2003).
- Badaev, S. A., Goncharov, S. S., Sorbi, A. “Completeness and Universality of Arithmetical Numberings”, in S. B. Cooper, S. S. Goncharov (Eds.), Computability and Models (Kluwer Academic/Plenum Publ., New York, 2003), 11–44.
- Badaev, S. A., Goncharov, S. S., and Sorbi, A. “Elementary Theories for Rogers Semilattices”, Algebra and Logic 44, No. 3, 143–147 (2005).
- Badaev, S. A., Goncharov, S. S. “Generalized Computable Universal Numberings”, Algebra and Logic 53, No. 5, 555–569 (2014).
- Ershov, Yu. L. Numeration Theory (Nauka, Moscow, 1977) [in Russian].
- Kalimullin, I., Faizrahmanov, M. “A Hierarchy of Classes of Families and n-Low Degrees”, Algebra and Logic 54, No. 4, 347–350 (2015).
- Faizrahmanov, M. K., Kalimullin, I. S. “The Enumeration Spectrum Hierarchy of n-Families”, Math. Log. Quat., 2016 (in press).
- Faizrahmanov, M., Kalimullin, I. “The Enumeration Spectrum Hierarchy of α-Families and Lowα Degrees”, J. Univ. Comp. Sci., 2016 (in press).