COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS

DENIS R. HIRSCHFELDT, CARL G. JOCKUSCH, RUTGER KUYPER, PAUL E. SCHUPP
  • Journal of Symbolic Logic, August 2016, Cambridge University Press
  • DOI: 10.1017/jsl.2015.70

What is it about?

A set is coarsely computable if it differs from a computable set on a set of asymptotic density 0. Thus coarse degrees are natural structures and the Turing degrees are embedded in the coarse degrees. There are deep connections between coarse degrees and algorithmic randomness.

The following have contributed to this page: Prof Paul E Schupp