Abstract:
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 $\phi$ 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.