Abstract
The theory of numberings studies uniform computations for families of mathematical objects. In this area, computability-theoretic properties of at most countable families of sets
Discover the SciOpen Platform and Achieve Your Research Goals with Ease.
The theory of numberings studies uniform computations for families of mathematical objects. In this area, computability-theoretic properties of at most countable families of sets
K. Gödel, On formally undecidable propositions of Principia Mathematica and related systems I, Monatsh. Math. Phys., vol. 38, no. 1, pp. 173–198, 1931.
S. C. Kleene, On notation for ordinal numbers, J. Symb. Log., vol. 3, no. 4, pp. 150–155, 1938.
A. N. Kolmogorov and V. A. Uspenskii, On the definition of an algorithm, (in Russian), Uspekhi Matematicheskikh Nauk, vol. 13, no. 4, pp. 3–28, 1958.
V. A. Uspenskii, Systems of denumerable sets and their enumeration, (in Russian), Doklady Akademii Nauk SSSR, vol. 105, pp. 1155–1158, 1958.
H. Rogers, Gödel numberings of partial recursive functions, J. Symb. Log., vol. 23, no. 3, pp. 331–341, 1958.
V. L. Selivanov, Two theorems on computable numberings, Algebra Logic, vol. 15, no. 4, pp. 297–306, 1976.
Y. L. Ershov, Necessary isomorphism conditions for Rogers semilattices of finite partially ordered sets, Algebra Logic, vol. 42, no. 4, pp. 232–236, 2003.
Y. L. Ershov, Rogers semilattices of finite partially ordered sets, Algebra Logic, vol. 45, no. 1, pp. 26–48, 2006.
M. Hoyrup and C. Rojas, Computability of probability measures and Martin-Löf randomness over metric spaces, Inf. Comput., vol. 207, no. 7, pp. 830–847, 2009.
A. B. Khutoretskii, On the cardinality of the upper semilattice of computable enumerations, Algebra Logic, vol. 10, no. 5, pp. 348–352, 1971.
Y. L. Ershov and I. A. Lavrov, The upper semilattice L (γ ), Algebra Logic, vol. 12, no. 2, pp. 93–106, 1973.
V. V. V’yugin, On some examples of upper semilattices of computable enumerations, Algebra Logic, vol. 12, no. 5, pp. 287–296, 1973.
S. S. Goncharov and A. Sorbi, Generalized computable numerations and nontrivial Rogers semilattices, Algebra Logic, vol. 36, no. 6, pp. 359–369, 1997.
S. A. Badaev, S. S. Goncharov, and A. Sorbi, Elementary theories for Rogers semilattices, Algebra Logic, vol. 44, no. 3, pp. 143–147, 2005.
S. A. Badaev, S. S. Goncharov, and A. Sorbi, Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy, Algebra Logic, vol. 45, no. 6, pp. 361–370, 2006.
S. Yu, Podzorov, Arithmetical D-degrees, Sib. Math. J., vol. 49, no. 6, pp. 1109–1123, 2008.
N. Bazhenov, M. Mustafa, and M. Yamaleev, Elementary theories and hereditary undecidability for semilattices of numberings, Arch. Math. Logic, vol. 58, nos. 3&4, pp. 485–500, 2019.
S. S. Goncharov, S. Lempp, and D. R. Solomon, Friedberg numberings of families of n-computably enumerable sets, Algebra Logic, vol. 41, no. 2, pp. 81–86, 2002.
S. A. Badaev and S. Lempp, A decomposition of the Rogers semilattice of a family of d.c.e. sets, J. Symb. Log., vol. 74, no. 2, pp. 618–640, 2009.
N. A. Bazhenov, M. Mustafa, S. S. Ospichev, and M. M. Yamaleev, Numberings in the analytical hierarchy, Algebra Logic, vol. 59, no. 5, pp. 404–407, 2020.
N. A. Bazhenov, M. Mustafa, and Z. Tleuliyeva, Theories of Rogers semilattices of analytical numberings, Lobachevskii J. Math., vol. 42, no. 4, pp. 701–708, 2021.
B. Balcar and T. Jech, Weak distributivity, a problem of von Neumann and the mystery of measurability, Bull. Symb. Log., vol. 12, no. 2, pp. 241–266, 2006.
N. Bazhenov, M. Harrison-Trainor, I. Kalimullin, A. Melnikov, and K. M. Ng, Automatic and polynomial-time algebraic structures, J. Symb. Log., vol. 84, no. 4, pp. 1630–1669, 2019.
W. Calvert and J. F. Knight, Classification from a computable viewpoint, Bull. Symb. Log., vol. 12, no. 2, pp. 191–218, 2006.
T. G. McLaughlin, The family of all recursively enumerable classes of finite sets, Trans. Am. Math. Soc., vol. 155, no. 1, pp. 127–136, 1971.
J. Harrison, Recursive pseudo well-orderings, Trans. Am. Math. Soc., vol. 131, no. 2, pp. 526–543, 1968.
W. M. White, On the complexity of categoricity in computable structures, Math. Log. Q., vol. 49, no. 6, pp. 603–614, 2003.
253
Views
42
Downloads
0
Crossref
0
Web of Science
0
Scopus
0
CSCD
Altmetrics
The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).