Event Detail

We consider algorithmic properties of additional relations on computable structures. For example, for a computable linear ordering we may consider the successor relation, which does not have to be computable. The degree spectrum of a relation on a computable structure is the set of degrees (Turing or other) of images of that relation under isomorphism to another computable copy of the structure. We’ll see a variety of examples of degree spectra of definable relations, and will use algorithmic information theory to analyze the strong degree spectra of the omega-type initial segment of computable linear orderings of type omega + omega*. I will discuss some general results, and present some examples from recent collaborative projects.