Algorithmic properties of structures and theories

One of the major questions of computable model theory is that of existence of computable structures with given model-theoretic and algebraic properties. To find conditions under which a theory has a computable model is one of the approaches to study this question. This question is especially interesting for classes of theories that are important from a model-theoretic point of view. The most advanced results in this direction are for countably categorical and uncountably categorical theories. The connected question is the question of uniqueness of a computable presentation for a structure up to computable isomorphism. To measure the complexity of isomorphisms between computable presentations of isomorphic structures, the notion of degree of categoricity is used. The question is what degrees can be presented as degrees of categoricity of computable structures. Another important question is that of classification of computable structures with fixed algorithmic, model- theoretic or algebraic properties. There are several approaches to estimate the complexity of classes of computable structures. One of them uses the notion of index set from the classical theory of numberings, where one talks about the complexity of a class of structures in terms of the complexity of its index set. A related question concerns the problem of classification of classes of computable structures up to some equivalence relation. The most interesting cases are the isomorphism relation and the bi-embeddability relation. We study this question by considering the indices of the corresponding class of computable structures. One of the goals of this project is to develop new methods for constructing computable structures with different algorithmic and model-theoretic properties of their theories. We aim to construct nonarithmetical countably categorical and uncountably categorical theories with computable models. We also study the complexity of isomorphisms between isomorphic copies of a given structure. Another goal is to study the algorithmic complexity of classes of computable structures and to compare the relations of isomorphism and bi-embeddability on such classes.