×

Effective choice for relations and reducibilities in classes of constructive and positive models. (English. Russian original) Zbl 0814.03030

Algebra Logic 31, No. 2, 63-73 (1992); translation from Algebra Logika 31, No. 2, 101-118 (1992).
Effective choice problems admit distinct variations in the classes of constructive and positive models, and, in most cases, have obvious formalizations. For an intrinsically recursively enumerable relation, for a constructivizable (i.e. recursive) autostable model, and for a positive autostable model, the author specifies the property of effective choice problems to be decidable.

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Yu. L. Ershov, Decidability Problems and Constructive Models [in Russian], Nauka, Moscow (1980).
[2] D. Scott, ”Logic with denumerable long formulas and finite strings of quantifiers”, in: The Theory of Models, North Holland, Amsterdam (1965). · Zbl 0166.26003
[3] S. S. Goncharov and V. D. Dzgoev, ”Autostability of models,” Algebra Logika,19, No. 2, 45–58 (1980). · Zbl 0468.03023
[4] C. J. Ash, ”Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees”, Trans. Am. Math. Soc.,298, No. 2, 497–514 (1986). · Zbl 0631.03017 · doi:10.1090/S0002-9947-1986-0860377-7
[5] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967). · Zbl 0183.01401
[6] V. A. Uspenskii and A. L. Semenov, Theory of Algorithms: Advances and Applications [in Russian], Moscow (1987).
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.