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.

Read Publication

http://dx.doi.org/10.1017/jsl.2015.70

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