Slides available at home.gwu.edu/∼jchubb

Linear orders and initial segments A linear order may be highly computable, but have complicated initial segments. Example (Q, <) is computable, but has initial segments of every Turing degree. Many important notions arise in our study of these objects... Π01 classes and ranked sets, Ideas from algorithmic complexity theory, Array non-computable degrees and totally ω-c.e. sets. Jennifer Chubb (GWU) Strong degree spectra and SCLOs CIE 21 June 2007 2 / 13 Starting point The (Turing) degree spectrum of a relation R on a structureM, DgSpM(R), is the collection of all Turing degrees of images of R in computable structures N ∼=M. Example (Harizanov, 1998) Let L be a computable linear order isomorphic to ω + ω∗, and ωL the ω-part of L. Then, the degree spectrum of ωL is exactly the ∆02-degrees