University Seminar- Computability, Complexity, and Algebraic Structure-Structural highness

Time: Friday, May 9, 2:30 – 3:30pm

Place: Phillips 209

Speaker:  Wesley Calvert, Southern Illinois University

Title: Structural highness

Abstract:  What kind of Turing degree is high enough to understand everything in computable structure theory?  In a series of papers with Franklin and Turetsky, we consider a range of answers to this question.
The original motivation was to consider degrees which are “high for isomorphism.” That is, given any two computable structures that are isomorphic, these degrees will compute an isomorphism between them.  In this sense, these degrees are dual both to those which are low for isomorphism and, in a different sense, to those which are degrees of categoricity.
The investigation breaks off into two directions: first, several other definitions of highness notions that in different ways capture structure-theoretic omniscience; and second, given a degree which is high in one of these senses, what an algorithm with this oracle trying to find an isomorphism would do if there were not one.