Geodesic
Uniformity in Computable Structure Theory
Algebra i logika, Tome 42 (2003) no. 5, pp. 566-593.

Voir la notice de l'article provenant de la source Math-Net.Ru

We investigate the effects of adding uniformity requirements to concepts in computable structure theory such as computable categoricity (of a structure) and intrinsic computability (of a relation on a computable structure). We consider and compare two different notions of uniformity, previously studied by Kudinov and by Ventsov. We discuss some of their results and establish new ones, while also exploring the connections with the relative computable structure theory of Ash, Knight, Manasse, and Slaman and Chisholm and with previous work of Ash, Knight, and Slaman on uniformity in a general computable structure-theoretical setting.
Keywords: computably categorical structure, intrinsically computable relation on a computable structure, relative computable structure, general computable structure. 
@article{AL_2003_42_5_a2,
     author = {R. Downey and D. Hirschfeldt and B. Khoussainov},
     title = {Uniformity in {Computable} {Structure} {Theory}},
     journal = {Algebra i logika},
     pages = {566--593},
     publisher = {mathdoc},
     volume = {42},
     number = {5},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2003_42_5_a2/}
}
TY  - JOUR
AU  - R. Downey
AU  - D. Hirschfeldt
AU  - B. Khoussainov
TI  - Uniformity in Computable Structure Theory
JO  - Algebra i logika
PY  - 2003
SP  - 566
EP  - 593
VL  - 42
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2003_42_5_a2/
LA  - ru
ID  - AL_2003_42_5_a2
ER  - 
%0 Journal Article
%A R. Downey
%A D. Hirschfeldt
%A B. Khoussainov
%T Uniformity in Computable Structure Theory
%J Algebra i logika
%D 2003
%P 566-593
%V 42
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2003_42_5_a2/
%G ru
%F AL_2003_42_5_a2
R. Downey; D. Hirschfeldt; B. Khoussainov. Uniformity in Computable Structure Theory. Algebra i logika, Tome 42 (2003) no. 5, pp. 566-593. http://geodesic.mathdoc.fr/item/AL_2003_42_5_a2/

[1] R. G. Downey, “Computability theory and linear orderings”, Handbook of recursive mathematics, Stud. Logic Found. Math., 139, eds. Y. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, Elsevier Science B.V., Amsterdam, 1998, 823–976 | MR | Zbl

[2] S. S. Goncharov, “Problema chisla neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 19:6 (1980), 621–639 | MR | Zbl

[3] P. Cholak, S. Goncharov, B. Khoussainov, R. A. Shore, “Computably categorical structures and expansions by constants”, J. Symb. Log., 64:1 (1999), 13–37 | DOI | MR | Zbl

[4] S. S. Goncharov, “O chisle neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 16:3 (1977), 257–282 | MR | Zbl

[5] T. Millar, “Recursive categoricity and persistence”, J. Symb. Log., 51:2 (1986), 430–434 | DOI | MR | Zbl

[6] C. J. Ash, J. F. Knight, M. S. Manasse, T. A. Slaman, “Generic copies of countable structures”, Ann. Pure Appl. Logic, 42:3 (1989), 195–205 | DOI | MR | Zbl

[7] J. Chisholm, “Effective model theory vs. recursive model theory”, J. Symb. Log., 55:3 (1990), 1168–1191 | DOI | MR | Zbl

[8] C. F. D. McCoy, “Finite computable dimension does not relativize”, Arch. Math. Logic, 41:4 (2002), 309–320 | DOI | MR | Zbl

[9] O. V. Kudinov, “Avtoustoichivaya 1-razreshimaya model bez vychislimogo semeistva Skotta $\exists$-formul”, Algebra i logika, 35:4 (1996), 458–467 | MR | Zbl

[10] O. V. Kudinov, “Nekotorye svoistva avtoustoichivykh modelei”, Algebra i logika, 35:6 (1996), 685–698 | MR | Zbl

[11] O. V. Kudinov, “Problema opisaniya avtoustoichivykh modelei”, Algebra i logika, 36:1 (1997), 26–36 | MR | Zbl

[12] Yu. G. Ventsov, “Problema effektivnogo vybora dlya otnoshenii i svodimostei v klassakh konstruktivnykh i pozitivnykh modelei”, Algebra i logika, 31:2 (1992), 101–118 | MR | Zbl

[13] Yu. G. Ventsov, “Effektivnye operatsii vybora na konstruktivnykh i pozitivnykh modelyakh”, Algebra i logika, 32:1 (1993), 45–53 | MR | Zbl

[14] C. J. Ash, J. F. Knight, T. A. Slaman, “Relatively recursive expansions. II”, Fundam. Math., 142:2 (1993), 147–161 | MR | Zbl

[15] R. I. Soare, Recursively enumerable sets and degrees, Perspect. Math. Logic, Springer-Verlag, Heidelberg, 1987 | MR

[16] W. Hodges, Model theory, Encycl. Math. Appl., 42, Cambridge University Press, Cambridge, 1993 | MR | Zbl

[17] C. J. Ash, J. F. Knight, “Relatively recursive expansions”, Fundam. Math., 140:2 (1992), 137–155 | MR | Zbl

[18] J. C. Shepherdson, J. Myhill, “Effective operations on partial recursive functions”, Z. Math. Logik Grundlag. Math., 1:4 (1955), 310–317 | DOI | MR | Zbl

[19] G. Kreisel, D. Lacombe, J. R. Shoenfield, “Partial recursive functionals and effective operations”, Constructivity in Mathematics: Proceedings of the Colloquium held at Amsterdam (1957), Stud. Logic Found. Math., ed. A. Heyting, North-Holland Publishing Co., Amsterdam, 1959, 195–207 | MR

[20] H. Rogers, Jr., Theory of recursive functions and effective computability, 2nd ed., MIT Press, Cambridge, Mass., 1987 | MR

[21] B. Khoussainov, R. A. Shore, “Computable isomorphisms, degree spectra of relations, and Scott families”, Ann. Pure Appl. Logic, 93:1–3 (1998), 153–193 | DOI | MR | Zbl

[22] V. V. Vyugin, “O diskretnykh klassakh rekursivno perechislimykh mnozhestv”, Algebra i logika, 11:3 (1972), 243–256

[23] C. J. Ash, A. Nerode, “Intrinsically recursive relations”, Aspects of effective algebra, Proc. conf. (1979), ed. J. N. Crossley, Monash Univ., Clayton, Aust., 1981, 26–41 | MR | Zbl

[24] M. S. Manasse, Techniques and counterexamples in almost categorical recursive model theory, PhD Thesis, University of Wisconsin, Madison, 1982

[25] J. Chisholm, “The complexity of intrinsically r.e. subsets of existentially decidable models”, J. Symb. Log., 55:3 (1990), 1213–1232 | DOI | MR | Zbl