Logic Seminar

Joey Lakerdas-Gayle, University of Waterloo

Weakly uniform computable categoricity

A computable structure A is Y-computably categorical if for every computable copy B of A, some isomorphism between A and B is computable in the oracle Y. Motivated by results about isomorphism spectra of computable structures, we introduce a relativized notion of uniform computable categoricity: For sets X and Yof natural numbers, we say that a computable structure A is weakly X-uniformly Y-computably categorical if A is Y-computably categorical and we can find Y-computable isomorphisms uniformly in X. We will investigate some natural questions about weakly uniform computable categoricity and compute some particular examples.

MC 5403