eng
episciences.org
Logical Methods in Computer Science
1860-5974
2014-12-24
Volume 10, Issue 4
10.2168/LMCS-10(4:15)2014
979
journal article
Sub-computable Boundedness Randomness
Sam Buss
Douglas Cenzer
Jeffrey B. Remmel
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.
https://lmcs.episciences.org/979/pdf
Computer Science - Logic in Computer Science