Coarse computabilty studies how well arbitrary sets can be approximated in terms of computable sets. Define two sets A and B of natural numbers to be coarsely similar, written A∼cB, if their symmetric difference A Δ B has density 0 in the sense of classical asymptotic density from number theory. This relation is an equivalence relation, so we consider the space 𝒮 = 𝒫(ℕ)/∼c of coarse similarity classes. There is a natural density metric defined on 𝒮 by setting δ(A,C) to be the upper density of their symmetric difference.
The space 𝒮 is very interesting. While neither separable nor compact, it is both complete and contractible. Indeed, 𝒮 is a geodesic metric space so it is a hyperbolic space in the sense of Gromov with the property that there are uncountably many different geodesics between any two distinct points of 𝒮. Define the core, or lower cone, κ(d), of a Turing degree d to be the family { [A] } of all classes of sets such that A ≤T d. The closure d̅ of the degree d is the closure of κ(d) in 𝒮.
Define the distance H(d,e) between two Turing degrees as the Hausdorff distance between their closures in 𝒮. This distance has an equivalent definition solely in terms of computability theory. It turns out that the the Hausdorff distance between any two degrees is either 0,1/2 or 1. This is joint work with Carl Jockusch.
This video is part of the New York Group Theory Cooperative‘s group theory seminar series.
