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

http://math.uchicago.edu/~drh/Papers/Papers/metric.pdf

### Logic and Computation Seminar

Tuesday, October 18, 2022 - 2:00pm

#### Denis Hirschfeldt

University of Chicago