zbMATH — the first resource for mathematics

Some effectively infinite classes of enumerations. (English) Zbl 0783.03022
Summary: This research partially answers the question raised by Goncharov about the size of the class of positive elements of a Rogers semilattice. We introduce a notion of effective infinity of classes of computable enumerations. Then, using finite injury priority method, we prove five theorems which give sufficient conditions to be effectively infinite for classes of all enumerations without repetitions, positive undecidable enumerations, negative undecidable enumerations and all computable enumerations of a family of r.e. sets. These theorems permit to strengthen the results of Pour-El, Howard, Ershov and Khutoretskij about existence of enumerations without repetitions and positive undecidable enumerations.
03D45 Theory of numerations, effectively presented structures
Full Text: DOI
[1] Yu.L., Ershov, The theory of enumerations, (1977), Nauka Moscow, (in Russian) · Zbl 0427.03037
[2] Ershov, Yu.L., On computable enumerations, Algebra and logic, 7, 5, 34-38, (1968) · Zbl 0273.02025
[3] Friedberg, R.N., Three theorems on recursive enumerations, J. symbolic logic, 23, 3, 309-316, (1958)
[4] S.S. Goncharov, Unique positive numeration, J. Symbolic Logic, to appear. · Zbl 0849.03035
[5] Khutoretskii, A.B., Two existence theorems for computable enumerations, Algebra and logic, 8, 4, 484-492, (1969)
[6] Kolmogorov, A.N.; Uspenskii, V.A., On the definition of algorithm, Uspehi matem. nauk, 13, 4, 3-28, (1958) · Zbl 0090.01101
[7] Malcev, A.I., Positive and negative enumerations, (), 379-383
[8] Pour-El, M.B., Gödel numbering verses friedberg numberings, Proc. amer. math. soc., 15, 2, 252-255, (1964) · Zbl 0168.25404
[9] Pour-El, M.B.; Howard, W., A structural criterion for recursive enumeration without repetition, Z. math. logic grundlag. math., 10, 8, 105-114, (1964) · Zbl 0132.24703
[10] Rogers, H., Theory of recursive functions and effective computability, (1967), McGraw-Hill New York · Zbl 0183.01401
[11] Rogers, H., Gödel numberings of partial recursive functions, J. symbolic logic, 23, 3, 331-341, (1958) · Zbl 0088.01602
[12] Soare, R.I., Recursively enumerable sets and degrees, (1987), Springer Berlin
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.