Imagen de Portada
Código QR

PROBABILISTIC ALGORITHMIC RANDOMNESS.

We introduce martingales defined by probabilistic strategies, in which randomness is used to decide whether to bet. We show that different criteria for the success of computable probabilistic strategies can be used to characterize ML-randomness, computable randomness, and partial computable randomne...

Descripción completa

Publicado en:Journal of Symbolic Logic Vol. 78; no. 2; pp. 579 - 602
Autores principales: BUSS, SAM, MINNES, MIA
Formato: Artículo
Publicado: Cambridge University Press Jun2013
Materias:
Martingales (Mathematics)
Probability theory
Kolmogorov complexity
Equivalence classes (Set theory)
Mathematical functions
Mathematical models
Acceso en línea:Ver este registro en EBSCOhost
Sumario:We introduce martingales defined by probabilistic strategies, in which randomness is used to decide whether to bet. We show that different criteria for the success of computable probabilistic strategies can be used to characterize ML-randomness, computable randomness, and partial computable randomness. Our characterization of ML-randomness partially addresses a critique of Schnorr by formulating ML randomness in terms of a computable process rather than a computably enumerable function.