RUS  ENG
Full version
SEMINARS



An asymptotic view of the theory of computability

Paul Schupp

University of Illinois at Urbana-Champaign



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.


© Steklov Math. Inst. of RAS, 2024