Abstract. We present a survey of results and open questions on various different notions of a spectrum which have been investigated by computable model theorists. The two best known notions are the spectrum of a structure and the spectrum of a relation on a computable structure. In both cases, the idea is to use Turing degrees to measure the complexity intrinsic to the structure or the relation. We will review how model theory has yielded new insights into computability theory, and vice versa, by means of these concepts.

We also introduce a third notion, the automorphism spectra, which is the set of all Turing degrees of nontrivial automorphisms of a fixed computable structure. The intention is to measure the complexity of the symmetries of the structure. This more recent concept is the subject of current work by Harizanov, Morozov and the speaker, and we present certain early results. An extra dimension to this investigation lies in the possibility of composing two automorphisms to get another; for structures and relations there is no analogous operation. In some cases results on automorphism spectra follow from or give rise to results on other spectra. As an example, we will show how our study of single-degree automorphism spectra led to the first known example of a structure whose spectrum contains exactly the high-n Turing degrees (those degrees whose n-th jump computes the (n+1)-st jump of the empty set).