COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS.

A coarse description of a set A ⊆ ω is a set D ⊆ ω such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in som...

Full description

Bibliographic Details

Published in:	Journal of Symbolic Logic Vol. 81; no. 3; pp. 1028 - 1047
Main Authors:	HIRSCHFELDT, DENIS R., JOCKUSCH, CARL G., KUYPER, RUTGER, SCHUPP, PAUL E.
Format:	Article
Published:	Cambridge University Press Sep2016
Subjects:	Algorithmic randomness Compact spaces (Topology) Random sets Unsolvability (Mathematical logic) Computable functions
Online Access:	View this record in EBSCOhost