Abstract
We outline the general approach to the notion of a computable numeration in the frames of which computable numerations, of families of arithmetic sets are studied.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
H. Rogers,Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
Yu. L. Ershov,Numeration Theory [in Russian], Nauka, Moscow (1977).
Yu. L. Ershov,Decidability Problems and Constructive Models [in Russian], Nauka, Moscow (1980).
A. I. Mal'tsev,Algorithms and Recursive Functions [in Russian], Nauka, Moscow (1965).
S. C. Kleene,Introduction to Metamathematics, Princeton, N. J. (1952).
A. N. Kolmogorov and V. A. Uspenskii, “Defining an Algorithm,”Usp. Mat. Nauk, 13, No. 4 (82), 2–28 (1958).
V. A. Uspenskii, “Systems of denumerable sets and their numerations,”Dok. Akad. Nauk SSSR, 105, No. 6, 1155–1158 (1955).
V. A. Uspenskii,Lectures on Computable Functions [in Russian], Fizmatgiz, Moscow (1960).
H. Rogers, “Gödel numberings of partial recursive functions,”J. Symb. Log., 23, No. 3, 331–341 (1958).
R. F. Friedberg, “Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication,”J. Symb. Log., 23, No. 3, 309–316 (1958).
I. A. Lavrov, “Computable numberings,” inProc. 5th Int. Congr. Logic, Methodology and Philosophy of Science, Part 1, Reidel, Dordrecht (1977), pp. 195–206.
M. B. Pour-El, “Gödel numberings versus Friedberg numberings,”Proc. Am. Math. Soc., 15, No. 2, 252–256 (1964).
M. B. Pour-El and H. Putnam, “Recursively enumerable classes and their applications to sequence of formal theories,”Arch. Math. Log. Gr., 8, 104–121 (1965).
S. S. Goncharov, “The problem of the number of non-autoequivalent constructivizations,”Dokl. Akad. Nauk SSSR, 251, No. 2, 271–274 (1980).
A. I. Maltsev, “Toward a theory of computable families of objects,”Algebra Logika, 3, No. 4, 5–31 (1964).
S. S. Goncharov, A. Yakhnis and V. Yakhnis, “Some effectively infinite classes of enumerations,”Ann. Pure Appl. Log., 60, 207–235 (1993).
Yu. L. Ershov,Definability and Computability [in Russian], Nauch. Kniga, Novosibirsk (1996).
A. B. Khutoretskii, “On the cardinality of the upper semilattice of computable numerations,”Algebra Logika, 10, No. 5, 561–569 (1971).
Additional information
Supported by RECO grant NERBCHRXCT 930415 and by RFFR grant No. 096-01-01525
Supported by RECO grant NERBCIPDCT 940615
Translated fromAlgebra i Logika, Vol. 36, No. 6, pp. 621–641, November-December, 1997.
Rights and permissions
About this article
Cite this article
Goncharov, S.S., Sorbi, A. Generalized computable numerations and nontrivial rogers semilattices. Algebr Logic 36, 359–369 (1997). https://doi.org/10.1007/BF02671553
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02671553