Examples



mdbootstrap.com



 
Статья
2016

Universal computable enumerations of finite classes of families of total functions


M. Kh. FaizrakhmanovM. 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
  1. Goncharov, S. S. and Sorbi, A. “Generalized Computable Numerations and Nontrivial Rogers Semilattices”, Algebra and Logic 36, No. 6, 359–369 (1997).
  2. Podzorov, S. Yu. “Initial Segments in Rogers Semilattices of Σ 0n -Computable Numberings”, Algebra and Logic 42, No. 2, 121–129 (2003).
  3. 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.
  4. Badaev, S. A., Goncharov, S. S., and Sorbi, A. “Elementary Theories for Rogers Semilattices”, Algebra and Logic 44, No. 3, 143–147 (2005).
  5. Badaev, S. A., Goncharov, S. S. “Generalized Computable Universal Numberings”, Algebra and Logic 53, No. 5, 555–569 (2014).
  6. Ershov, Yu. L. Numeration Theory (Nauka, Moscow, 1977) [in Russian].
  7. Kalimullin, I., Faizrahmanov, M. “A Hierarchy of Classes of Families and n-Low Degrees”, Algebra and Logic 54, No. 4, 347–350 (2015).
  8. Faizrahmanov, M. K., Kalimullin, I. S. “The Enumeration Spectrum Hierarchy of n-Families”, Math. Log. Quat., 2016 (in press).
  9. Faizrahmanov, M., Kalimullin, I. “The Enumeration Spectrum Hierarchy of α-Families and Lowα Degrees”, J. Univ. Comp. Sci., 2016 (in press).