Imagen de Portada
Código QR

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

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
Sumario: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 relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.