Friday, February 21, 2003
2:30 pm, Science 2-066

Russell Miller

Cornell University

Characterizing Computability through Model Theory

Abstract: Beginning with the basic definitions of computability and the Turing degrees, we will look for a form of information which characterizes the Turing-non-computable sets, in the sense that a set is non-computable if and only if it contains this information. The first try, in which we consider sets themselves as forms of information, fails: we will briefly the construction of a "minimal pair" of sets $A$ and $B$ such that any set computable both from $A$ and from $B$ is in fact computable from the empty set, which has no information content. However, when we consider mathematical structures of greater complexity, our search succeeds. We will describe the results of Slaman and Wehner, that there exist structures which can be computed by $A$ iff $A$ itself is non-computable. Finally, we will ask which types of structures can have this property, considering groups, Boolean algebras, and linear orders, among others, and discussing results by several logicians including the speaker.