This paper defines a new notion of bounded computable randomness for certainclasses of sub-computable functions which lack a universal machine. Inparticular, we define such versions of randomness for primitive recursivefunctions and for PSPACE functions. These new notions are robust in that thereare equivalent formulations in terms of (1) Martin-L"of tests, (2) Kolmogorovcomplexity, and (3) martingales. We show these notions can be equivalentlydefined with prefix-free Kolmogorov complexity. We prove that one direction ofvan Lambalgen's theorem holds for relative computability, but the otherdirection fails. We discuss statistical properties of these notions ofrandomness.
展开▼
机译：本文为某些缺乏通用机器的亚可计算函数类定义了一种有界可计算随机性的新概念。特别是，我们为原始递归函数和PSPACE函数定义了这种随机性版本。这些新概念很健壮，因为在（1）测试的Martin-L“，（2）Kolmogorov复杂度和（3）mar等方面存在等效的表示形式。我们证明了可以用无前缀的Kolmogorov复杂度等效地定义这些概念。 Van Lambalgen定理的一个方向对于相对可计算性成立，但另一个方向却失败了，我们讨论了这些随机性概念的统计性质。
展开▼
