Effectively infinite classes of numberings and fixed point theorems. (Russian. English summary) Zbl 07896842
Summary: In this paper, we prove a sufficient condition for the effective infinity of classes of complete and precomplete numberings, as well as numberings satisfying the recursion theorem, of computable families. A sufficient condition for the effective infinity of classes of non-precomplete numberings of computable families satisfying the recursion theorem is also obtained. These conditions are satisfied by the family of all c.e. sets and the family of graphs of all partially computable functions. For finite families of c.e. sets, we prove a criterion for the effective infinity of classes of their numberings that satisfy the recursion theorem. Finally, it is established that the classes of complete and precomplete numberings of finite families of c.e. sets are not effectively infinite.
MSC:
| 03D45 | Theory of numerations, effectively presented structures |
Keywords:
computable numbering; complete numbering; precomplete numbering; recursion theorem; effective infinityReferences:
| [1] | S.S. Goncharov, A. Yakhnis, V. Yakhnis, “Some effectively infinite classes of enumerations”, Ann. Pure App. Logic, 60:3 (1993), 207-235 · Zbl 0783.03022 · doi:10.1016/0168-0072(93)90076-P |
| [2] | A.I. Mal’tsev, “Completely enumerated sets”, Algebra Logika, 2:2 (1963), 4-29 · Zbl 0163.00802 |
| [3] | A.I. Mal’tsev, The metamathematics of algebraic systems, North-Holland, Amsterdam-London, 1971 |
| [4] | Yu.L. Ershov, “Theorie der numerierungen I”, Z. Math. Log. Grundl. Math., 19 (1973), 289-388 · Zbl 0295.02025 · doi:10.1002/malq.19730191901 |
| [5] | Yu.L. Ershov, Theory of numberings, Nauka, M., 1977 |
| [6] | Yu.L. Ershov, “Completely enumerated sets”, Sib. Math. J., 10 (1970), 773-784 · Zbl 0323.02054 · doi:10.1007/BF00971653 |
| [7] | Yu.L. Ershov, “On inseparable pairs”, Algebra Logic, 9:6 (1972), 396-399 · Zbl 0263.02021 · doi:10.1007/BF02219043 |
| [8] | V.L. Selivanov, “Index sets of quotient objects of the Post numeration”, Algebra Logic, 27:3 (1988), 215-224 · Zbl 0688.03027 · doi:10.1007/BF01978567 |
| [9] | S.A. Badaev, S.S. Goncharov, A. Sorbi, “Completeness and universality of arithmetical numberings”, Computability and Models, Univ. Ser. Math., Kluwer Academic/Plenum Publishers, New York, 2003, 11-44 · Zbl 1104.03001 · doi:10.1007/978-1-4615-0755-0_2 |
| [10] | H. Barendregt, S.A. Terwijn, “Fixed point theorems for precomplete numberings”, Ann. Pure App. Logic, 170:10 (2019), 1151-1161 · Zbl 1454.03049 · doi:10.1016/j.apal.2019.04.013 |
| [11] | M.M. Arslanov, “Fixed-point selection functions”, Lobachevskii J. Math., 42:4 (2021), 685-692 · Zbl 1491.03030 · doi:10.1134/S1995080221040041 |
| [12] | V.L. Selivanov, “Precomplete numberings”, J. Math. Sci., New York, 256:1 (2021), 96-124 · Zbl 1535.03224 · doi:10.1007/s10958-021-05422-2 |
| [13] | T.H. Payne, “Effective extendability and fixed-points”, Notre Dame J. Formal Logic, 14:1 (1973), 123-124 · Zbl 0236.02039 · doi:10.1305/ndjfl/1093890819 |
| [14] | S.A. Badaev, “On weakly pre-complete positive equivalences”, Sib. Math. J., 32:2 (1991), 321-323 · Zbl 0733.03034 · doi:10.1007/BF00972779 |
| [15] | M. Faizrahmanov, “Extremal numberings and fixed point theorems”, Math. Log. Q., 68:4 (2022), 398-408 · Zbl 1521.03129 · doi:10.1002/malq.202200035 |
| [16] | Yu.L. Ershov, “Theory of numberings”, Handbook of computability theory, Elsevier. Stud. Logic Found. Math., 140, ed. Griffor Edward R., Elsevier, Amsterdam, 1999, 473-503 · Zbl 0948.03040 · doi:10.1016/S0049-237X(99)80030-5 |
| [17] | R.I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin etc., 1987 · Zbl 0623.03042 · doi:10.1007/978-3-662-02460-7 |
| [18] | R.I. Soare, Turing computability. Theory and applications, Springer, Berlin, 2016 · Zbl 1350.03001 · doi:10.1007/978-3-642-31933-4 |
| [19] | Yu.L. Ershov, “Theorie der numerierungen II”, Z. Math. Log. Grundl. Math., 21:1 (1975), 473-584 · Zbl 0344.02031 · doi:10.1002/malq.19750210164 |
| [20] | R.M. Friedberg, “Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication”, J. Symb. Log., 23:3 (1959), 309-316 · Zbl 0088.01601 · doi:10.2307/2964290 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
