CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS.

We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15] (also Problem 5.5.19 in [34]). We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativizatio...

Descripción completa

Detalles Bibliográficos

Publicado en:	Journal of Symbolic Logic Vol. 79; no. 2; pp. 526 - 561
Autores principales:	BIENVENU, LAURENT, DOWNEY, ROD, GREENBERG, NOAM, NIES, ANDRÉ, TURETSKY, DAN
Formato:	Artículo
Publicado:	Cambridge University Press Jun2014
Materias:	Set theory Computable functions Algorithmic randomness Turing machines Random sets
Acceso en línea:	Ver este registro en EBSCOhost