Computable Isomorphisms, Degree Spectra of Relations, and Scott Families

Abstract

In studying effective structures we investigate the effective content of typical notions and constructions in many branches of mathematics including universal algebra and model theory. In particular, we are interested in the possibilities of effectivizing model-theoretic or algebraic constructions and the limits on these possibilities. For instance, we try to understand whether certain results of model theory (or universal algebra) can be carried out effectively. If not, we then try to discover sharp effective counterexamples. The systematic study of effectiveness in algebraic structures goes back to pioneering papers by Frölich and Shepherdson [11], Malcev [28][29], and Rabin [34] in the early 60s. Later in the early 70s, Nerode and his collaborators initiated combining algebraic constructions with priority arguments from computability theory thus beginning a new era in the development of the subject. Nowadays, there various approaches to effectiveness in structures. For example, Cenzer, Nerode, Remmel have been developing theory of p-time structures [6]. Khoussainov and Nerode have began the development of the theory of automatic structures [27]. In this paper we are interested in those structures in which the basic computations can be performed by Turing machines.