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.