The Scott rank of a countable structure is a measure, coming from the proof of Scott's isomorphism theorem, of the complexity of that structure. The Scott spectrum of a theory (by which we mean a sentence of $\mc{L}_{\omega_1 \omega}$) is the set of Scott ranks of countable models of that theory. In $ZFC + PD$ we give a descriptive-set-theoretic classification of the sets of ordinals which are the Scott spectrum of a theory: they are particular $\bfSigma^1_1$ classes of ordinals.

Our investigation of Scott spectra leads to the resolution (in $ZFC$) of a number of open problems about Scott ranks. We answer a question of Montalb an by showing, for each $\alpha < \omega_1$, that there is a $\Pi^{\infi}_2$ theory with no models of Scott rank less than $\alpha$. We also answer a question of Knight and Calvert by showing that there are computable models of high Scott rank which are not computably approximable by models of low Scott rank. Finally, we answer a question of Sacks and Marker by showing that $\delta^1_2$ is the least ordinal $\alpha$ such that if the models of a computable theory $T$ have Scott rank bounded below $\omega_1$, then their Scott ranks are bounded below $\alpha$.

We prove various results about the complexity of countable structures, both computable and arbitrary.

We begin by investigating descriptions of countable structures in the infinitary logic L_ω1ω. Given a countable structure A, we can find a sentence ϕ, a Scott sentence for A, which describes A up to isomorphism in the sense that A is the unique countable model of ϕ. We can assign a complexity, the Scott rank of A, to A; this is the quantifier complexity of the simplest Scott sentence. We investigate the Scott ranks of the models of a theory; we produce several new computable models of high Scott rank; we construct a computable group with no d-Σ₂ Scott sentence; and we produce a first-order theory of Ulm type.

Next, we look at computable structures on a cone. If A is a natural structure—by which we mean an informal notion of a structure that might show up in the normal course of mathematics, and which was not constructed explicitly as a computability-theoretic counterexample—then arguments about A will generally relativize. So we can study natural structures by studying arbitrary structures relativized "on a cone". This gives us a way of making precise statements about the imprecise notion of a natural structure. We give a complete classification of the degrees of categoricity on a cone, and prove a number of results about degree spectra of relation on a cone.

Third, we investigate the deep connections between infinitary interpretations and functors. An interpretation of one structure A in another structure B induces a functor which produces copies of A from copies of B. Moreover, the interpretation induces a homomorphism from the automorphism group of B to the automorphism group of A. We show that this reverses: given a functor from B to A, or a homomorphism from the automorphism group of B to A, we can recover an interpretation. We consider the effective version of this, as well as the corresponding results for bi-interpretations.

Finally, we look at a number of different algebraic structures. We study the effectivization of extending automorphisms of fields to their algebraic closure, extending valuations to a field extension, and embedding valued fields into algebraically closed valued fields. We give a metatheorem for finding computable copies of various algebraic structures with an independence relation, such as differentially closed fields with δ-independence, with a computable basis. We show that there is a computable left-orderable group with no computable copy with a computable ordering.