May 14, 2015. Paul Schupp (University of Illinois at Urbana-Champaign). AN ASYMPTOTIC VIEW OF THE THEORY OF COMPUTABILITY.

In recent years the asymptotic-generic point of view of geometric group theory has led to new developments in the theory of computability. I will try to explain this starting from basics. The talk will be for a general audience.

The basic idea is to use asymptotic density as a measure of "for almost all". A set A is generically computable if there is a partial algorithm φ for A whose domain has asymptotic density 1. A set A is coarsely computable if there is a computable set C such that the symmetric difference of A and C has density 0. Natural questions from this point of view turn out to be very closely linked to classical ideas in computability theory.

For example, a c.e. degree d is not low if and only if d contains a c.e. set A with density 1 which does not have any computable subset of density 1. It turns out that there is a very tight connection between the position of a set in the arithmetic hierarchy and the complexities of its densities as real numbers.

List of talks at previous sessions of the seminar.