Geodesic
Automorphism Groups of Computably Enumerable Predicates
Algebra i logika, Tome 41 (2002) no. 5, pp. 515-530.

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

We study automorphism groups of two important predicates in computability theory: the predicate $x\in W_y$ and the graph of a universal partially computable function. It is shown that all automorphisms of the predicates in question are computable. The actions of the automorphism groups on some index sets are examined, and we establish a number of results on the structure of these. We also look into homomorphisms of the two predicates. In this case the situation changes: all homomorphisms of the universal function are computable, but in each Turing degree, homomorphisms of $x\in W_y$ exist.
Mots-clés : automorphism group, homomorphism
Keywords: computably enumerable predicate. 
@article{AL_2002_41_5_a0,
     author = {E. Combarro},
     title = {Automorphism {Groups} of {Computably} {Enumerable} {Predicates}},
     journal = {Algebra i logika},
     pages = {515--530},
     publisher = {mathdoc},
     volume = {41},
     number = {5},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2002_41_5_a0/}
}
TY  - JOUR
AU  - E. Combarro
TI  - Automorphism Groups of Computably Enumerable Predicates
JO  - Algebra i logika
PY  - 2002
SP  - 515
EP  - 530
VL  - 41
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2002_41_5_a0/
LA  - ru
ID  - AL_2002_41_5_a0
ER  - 
%0 Journal Article
%A E. Combarro
%T Automorphism Groups of Computably Enumerable Predicates
%J Algebra i logika
%D 2002
%P 515-530
%V 41
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2002_41_5_a0/
%G ru
%F AL_2002_41_5_a0
E. Combarro. Automorphism Groups of Computably Enumerable Predicates. Algebra i logika, Tome 41 (2002) no. 5, pp. 515-530. http://geodesic.mathdoc.fr/item/AL_2002_41_5_a0/

[1] H. B. Enderton, “Elements of recursion theory”, Handbook of mathematical logic, ed. J. Barwise, North-Holland, New York, 1977 | MR

[2] P. Odifreddi, Classical recursion theory, North-Holland, Amsterdam, 1989 | MR | Zbl

[3] M. Blum, I. Marques, “On complexity properties of recursively enumerable sets”, J. Symb. Log., 38:4 (1973), 579–593 | DOI | MR

[4] J. Barwise, “Back and forth through infinitary logic”, Studies in model theory, MAA Stud. Math., 8, ed. M. D. Morley, DC, Math. Assoc. Am., Washington, 1973, 5–34 | MR

[5] D. Kueker, “Definability, automorphisms and infinitary languages”, The syntax and semantics of infinitary languages, Lect. Notes Math., 72, Springer-Verlag, Berlin, 1968, 152–165 | MR

[6] J. J. Rotman, The theory of groups, Allyn and Bacon, Boston, 1965 | MR | Zbl

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

[8] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977 | MR