Sub-computable Boundedness Randomness

DOI10.2168/LMCS-10(4:15)2014MaRDI QIDQ2938768zbMATH OpenOpenAlexFDO

Authors Douglas Cenzer, Samuel R. Buss, Jeffrey Remmel

Publication date 15 January 2015

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.3995

zbMATH Keywords

algorithmic randomnesspolynomial spaceprimitive recursivesubcomputable classes

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32)

Abstract: This paper defines a new notion of bounded computable randomness for certain classes of sub-computable functions which lack a universal machine. In particular, we define such versions of randomness for primitive recursive functions and for PSPACE functions. These new notions are robust in that there are equivalent formulations in terms of (1) Martin-L"of tests, (2) Kolmogorov complexity, and (3) martingales. We show these notions can be equivalently defined with prefix-free Kolmogorov complexity. We prove that one direction of van Lambalgen's theorem holds for relative computability, but the other direction fails. We discuss statistical properties of these notions of randomness.

Recommendations

• Sub-computable bounded pseudorandomness
• Subcomputable Schnorr randomness
• scientific article; zbMATH DE number 1531917
• scientific article; zbMATH DE number 512979
• Bounded randomness
• Computability and Randomness
• Computability and randomness
• Randomness for computable measures and initial segment complexity
• Computability, algorithmic randomness and complexity
• Randomness and the linear degrees of computability

Cited in

(4)

• Subcomputable Hausdorff function dimension
• Bounded randomness
• Subcomputable Schnorr randomness
• Sub-computable bounded pseudorandomness

This page was built for publication: Sub-computable Boundedness Randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938768)