Abstract:
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.