Kurt Gödel Research Center

2013 seminar talk: Lowness in recursive model theory

Talk held by Johanna Franklin (University of Connecticut, USA) at the KGRC seminar on 2013-06-20.

Abstract

We say that a Turing degree is low in a particular context if using it as an oracle in that context has the same result as using no oracle at all. Lowness has been studied in the frameworks of degree theory, learning theory, and randomness. I will discuss lowness in recursive model theory: we say that a degree is low for isomorphism if, whenever it can compute an isomorphism between two recursively presented structures, there is actually a recursive isomorphism between them. I will describe the class of Turing degrees that are low for isomorphism, identify some particular subclasses, and show how it behaves with respect to measure and category.

This work is joint with Reed Solomon.