Geodesic
The computable embedding problem
Algebra i logika, Tome 50 (2011) no. 6, pp. 707-732.

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

Calvert calculated the complexity of the computable isomorphism problem for a number of familiar classes of structures. Rosendal suggested that it might be interesting to do the same for the computable embedding problem. By the computable isomorphism problem and (computable embedding problem) we mean the difficulty of determining whether there exists an isomorphism (embedding) between two members of a class of computable structures. For some classes, such as the class of $\mathbb Q$-vector spaces and the class of linear orderings, it turns out that the two problems have the same complexity. Moreover, calculations are essentially the same. For other classes, there are differences. We present examples in which the embedding problem is trivial (within the class) and the computable isomorphism problem is more complicated. We also give an example in which the embedding problem is more complicated than the isomorphism problem.
Keywords: computable structure, computable isomorphism problem, computable embedding problem. 
@article{AL_2011_50_6_a2,
     author = {J. Carson and E. Fokina and V. S. Harizanov and J. F. Knight and S. Quinn and C. Safranski and J. Wallbaum},
     title = {The computable embedding problem},
     journal = {Algebra i logika},
     pages = {707--732},
     publisher = {mathdoc},
     volume = {50},
     number = {6},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2011_50_6_a2/}
}
TY  - JOUR
AU  - J. Carson
AU  - E. Fokina
AU  - V. S. Harizanov
AU  - J. F. Knight
AU  - S. Quinn
AU  - C. Safranski
AU  - J. Wallbaum
TI  - The computable embedding problem
JO  - Algebra i logika
PY  - 2011
SP  - 707
EP  - 732
VL  - 50
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2011_50_6_a2/
LA  - ru
ID  - AL_2011_50_6_a2
ER  - 
%0 Journal Article
%A J. Carson
%A E. Fokina
%A V. S. Harizanov
%A J. F. Knight
%A S. Quinn
%A C. Safranski
%A J. Wallbaum
%T The computable embedding problem
%J Algebra i logika
%D 2011
%P 707-732
%V 50
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2011_50_6_a2/
%G ru
%F AL_2011_50_6_a2
J. Carson; E. Fokina; V. S. Harizanov; J. F. Knight; S. Quinn; C. Safranski; J. Wallbaum. The computable embedding problem. Algebra i logika, Tome 50 (2011) no. 6, pp. 707-732. http://geodesic.mathdoc.fr/item/AL_2011_50_6_a2/

[1] S. S. Goncharov, Dzh. Nait, “Vychislimye strukturnye i antistrukturnye teoremy”, Algebra i logika, 41:6 (2002), 639–681 | MR | Zbl

[2] C. J. Ash, J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Stud. Logic Found. Math., 144, Elsevier Sci. B.V., Amsterdam etc., 2000 | MR | Zbl

[3] R. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967 ; Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR | Zbl | MR

[4] W. Calvert, Algebraic structure and computable structure, PhD thesis, Notre Dame Univ., 2005 | MR

[5] W. Calvert, “The isomorphism problem for classes of computable fields”, Arch. Math. Log., 43:3 (2004), 327–336 | DOI | MR | Zbl

[6] W. Calvert, “The isomorphism problem for computable Abelian $p$-groups of bounded length”, J. Symb. Log., 70:1 (2005), 331–345 | DOI | MR | Zbl

[7] J. F. Knight, S. Miller, M. Vanden Boom, “Turing computable embeddings”, J. Symb. Log., 72:3 (2007), 901–918 | DOI | MR | Zbl

[8] R. Downey, A. Montalbán, “The isomorphism problem for torsion free Abelian groups is analytic complete”, J. Algebra, 320:6 (2008), 2291–2300 | DOI | MR | Zbl

[9] V. Harizanov, S. Lempp, C. F. D. McCoy, A. S. Morozov, D. Reed Solomon, On the isomorphism problem for nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups, preprint

[10] D. Marker, Model theory: An Introduction, Grad. Texts Math., 217, Springer-Verlag, New York, 2002 | MR | Zbl

[11] U. Kalvert, D. Kammins, Dzh. F. Nait, S. Miller, “Sravnenie klassov konechnykh struktur”, Algebra i logika, 43:6 (2004), 666–701 | MR | Zbl

[12] H. Friedman, L. Stanley, “A Borel reducibility theory for classes of countable structures”, J. Symb. Log., 54:3 (1989), 894–914 | DOI | MR | Zbl

[13] A. I. Maltsev, “Ob odnom sootvetstvii mezhdu koltsami i gruppami”, Matem. cb., 50(92):3 (1960), 257–266 ; A. Mal'cev, “On a correspondence between rings and groups”, Am. Math. Soc. Trans. Ser. 2, 45, 1965, 221–232 | MR | Zbl

[14] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, A. M. Slinko, “Degree spectra and computable dimensions in algebraic structures”, Ann. Pure Appl. Logic, 115:1–3 (2002), 71–113 | DOI | MR | Zbl

[15] R. C. Lyndon, P. E. Schupp, Combinatorial group theory, Ergebn. Math. Grenzg., 89, Springer-Verlag, Berlin–Heidelberg–New York, 1977 ; R. Lindon, P. Shupp, Kombinatornaya teoriya grupp, Mir, M., 1980 | MR | Zbl | MR

[16] G. Higman, B. H. Neumann, H. Neumann, “Embedding theorems for groups”, J. Lond. Math. Soc., 24 (1950), 247–254 | DOI | MR | Zbl

[17] G. S. Sacerdote, “Elementary properties of free groups”, Trans. Am. Math. Soc., 178 (1973), 127–138 | DOI | MR | Zbl

[18] W. Calvert, D. Cenzer, V. Harizanov, A. Morozov, “Effective categoricity of equivalence structures”, Ann. Pure Appl. Logic, 141:1–2 (2006), 61–78 | DOI | MR | Zbl

[19] C. J. Ash, J. F. Knight, “Pairs of recursive structures”, Ann. Pure Appl. Logic, 46:3 (1990), 211–234 | DOI | MR | Zbl

[20] A. T. Nurtazin, Vychislimye klassy i algebraicheskii kriterii avtoustoichivosti, Kand. diss., In-t matem. mekh., Alma-Ata, 1974