Logic Seminar

Java Villano, University of Toronto

Relativizing computable categoricity

A computable structure A is said to be computably categorical if for all computable copies B of A, there exists a computable isomorphism between A and B. We can relativize this notion to any Turing degree d by asking that for any d-computable copy B of A, there is a d-computable isomorphism between A and B. In this talk, we will discuss results about this relativization. In particular, we will discuss how for directed graphs, categoricity relative to a degree need not be monotonic in the c.e.~ degrees, and how for other structures besides directed graphs, categorical behavior relative to a degree stabilizes on certain Turing cones.

MC 5403