This book describes a program of research in computable structure theory. The goal is to
find definability conditions corresponding to bounds on complexity which persist under …

The theory of constructive (recursive) models follows from works of Froehlich, Shepherdson,
Mal'tsev, Kuznetsov, Rabin, and Vaught in the 50s. Within the framework of this theory …

We exploit properties of certain directed graphs, obtained from the families of sets with
special effective enumeration properties, to generalize several results in computable model …

Publisher Summary This chapter discusses the computability theory or recursion theory with
attempts to understand the algorithmic nature of the universe; combinatorics particularly …

In mathematics, we know there are some concepts-objects, constructions, structures, proofs-
that are more complex and difficult to describe than others. Computable structure theory …

3. Theories, types, models, and diagrams. 138 4. Small theories and their models. 144 5.
Effective categoricity. 148 6. Automorphisms of effective structures. 156 7. Degree spectra of …

Publisher Summary This chapter discusses the foundations of computable model theory: the
definitions and examples of decidable theories and computable and decidable models …

Our main result is the equivalence of two notions of reducibility between structures. One is a
syntactical notion which is an effective version of interpretability as in model theory, and the …

We investigate effective categoricity of computable equivalence structures A. We show that A
is computably categorical if and only if A has only finitely many finite equivalence classes, or …

The notion of computability in mathematics and technics has become a subject of great
interest and study. This is largely motivated by the rapid development and use of computers …