The main theme of this thesis is studying classes of structures with respect to various measurements of complexity. We will briefly discuss the notion of computable dimension, while the breadth of the paper will focus on calculating the Turing ordinal and the back-and-forth ordinal of various classes, along with an exploration of how these two ordinals are related in general. Computable structure theorists study which computable dimensions can be realized by structures from a given class. Using a structural characterization of the computably categorical equivalence structures due to Calvert, Cenzer, Harizanov and Morozov, we prove that the only possible computable dimension of an equivalence structure is 1 or ω. In 1994, Jockusch and Soare introduced the notion of the Turing ordinal of a class of structures. It was unknown whether every computable ordinal was the Turing ordinal of some class. Following the work of Ash, Jocksuch and Knight, we show that the answer is yes, but, as one might expect, the axiomatizations of these classes are complex. In 2009, Montalban defined the back-and-forth ordinal of a class using the back-and-forth relations. Montalban, following a result of Knight, showed that if the back-and-forth ordinal is n+1, then the Turing ordinal is at least n. We will prove a theorem stated by Knight that extends the previous result to all computable ordinals and show that if the back-and-forth ordinal is α (infinite) then the Turing ordinal is at least α. It is conjectured at present that if a class of structures is relatively nice then the Turing ordinal and the back-and-forth ordinal of the class differ by at most 1. We will present many examples of classes having axiomatizations of varying complexities that support this conjecture; however, we will show that this result does not hold for arbitrary Borel classes. In particular, we will prove that there is a Borel class with infinite Turing ordinal but finite back-and-forth ordinal and show that, for each positive integer d, there exists a Borel class of structures such that the Turing ordinal and the back-and-forth ordinal of the class are both finite and differ by at least d.

The main theme of this thesis is studying classes of structures with respect to various measurements of complexity. We will briefly discuss the notion of computable dimension, while the breadth of the paper will focus on calculating the Turing ordinal and the back-and-forth ordinal of various classes, along with an exploration of how these two ordinals are related in general. Computable structure theorists study which computable dimensions can be realized by structures from a given class. Using a structural characterization of the computably categorical equivalence structures due to Calvert, Cenzer, Harizanov and Morozov, we prove that the only possible computable dimension of an equivalence structure is 1 or ω. In 1994, Jockusch and Soare introduced the notion of the Turing ordinal of a class of structures. It was unknown whether every computable ordinal was the Turing ordinal of some class. Following the work of Ash, Jocksuch and Knight, we show that the answer is yes, but, as one might expect, the axiomatizations of these classes are complex. In 2009, Montalban defined the back-and-forth ordinal of a class using the back-and-forth relations. Montalban, following a result of Knight, showed that if the back-and-forth ordinal is n+1, then the Turing ordinal is at least n. We will prove a theorem stated by Knight that extends the previous result to all computable ordinals and show that if the back-and-forth ordinal is α (infinite) then the Turing ordinal is at least α. It is conjectured at present that if a class of structures is relatively nice then the Turing ordinal and the back-and-forth ordinal of the class differ by at most 1. We will present many examples of classes having axiomatizations of varying complexities that support this conjecture; however, we will show that this result does not hold for arbitrary Borel classes. In particular, we will prove that there is a Borel class with infinite Turing ordinal but finite back-and-forth ordinal and show that, for each positive integer d, there exists a Borel class of structures such that the Turing ordinal and the back-and-forth ordinal of the class are both finite and differ by at least d.

Let X be a unary relation on the domain of (ω,<). The degree spectrum of X on (ω,<) is the set of Turing degrees of the image of X in all computable presentations of (ω,<). Many results are known about the types of degree spectra that are possible for relations forming infinite and coinfinite c.e. sets, high c.e. sets and non-high c.e. sets on the standard copy. We show that if the degree spectrum of X contains the computable degree then its degree spectrum is precisely the set of Δ_2 degrees. The structure ζ can be viewed as a copy of ω* followed by a copy of ω and, for this reason, the degree spectrum of X on ζ can be largely understood from the work on ω. A helpful correspondence between the degree spectra on ω and ζ is presented and the known results for degree spectra on the former structure are extended to analogous results for the latter.

Let X be a unary relation on the domain of (ω,<). The degree spectrum of X on (ω,<) is the set of Turing degrees of the image of X in all computable presentations of (ω,<). Many results are known about the types of degree spectra that are possible for relations forming infinite and coinfinite c.e. sets, high c.e. sets and non-high c.e. sets on the standard copy. We show that if the degree spectrum of X contains the computable degree then its degree spectrum is precisely the set of Δ_2 degrees. The structure ζ can be viewed as a copy of ω* followed by a copy of ω and, for this reason, the degree spectrum of X on ζ can be largely understood from the work on ω. A helpful correspondence between the degree spectra on ω and ζ is presented and the known results for degree spectra on the former structure are extended to analogous results for the latter.