Penn Arts & Sciences Logo

Logic and Computation Seminar

Tuesday, October 18, 2022 - 2:00pm

Denis Hirschfeldt

University of Chicago


University of Pennsylvania

online (contact Henry Towsner for link)

I will discuss joint work with Carl G. Jockusch, Jr. and
Paul E. Schupp on computability-theoretic aspects of the distance
function on the power set of the natural numbers given by the upper
density of the symmetric difference of two sets. Two sets are coarsely
equivalent if this density is zero. Modding out by this equivalence
relation yields a metric space, which also allows us to define a
notion of distance between Turing degrees using the Hausdorff
metric. This metric turns out to be (0, 1/2, 1)-valued, by the
relativized version of a theorem of Monin, and its analysis is closely
connected with the interplay between randomness and genericity in
computability theory. Our paper is available at