The probability distribution as a computational resource for randomness testing

Bjørn Kjos-Hanssen


When testing a set of data for randomness according to a probability distribution that depends on a parameter, access to this parameter can be considered as a computational resource. We call a randomness test \emph{Hippocratic} if it is not permitted to access this resource. In these terms, we show that for Bernoulli measures $\mu_p$, $0\le p\le 1$ and the Martin-L\"of randomness model, Hippocratic randomness of a set of data is the same as ordinary randomness. The main idea of the proof is to first show that from Hippocrates-random data one can Turing compute the parameter $p$. However, we show that there is no single Hippocratic randomness test such that passing the test implies computing $p$, and in particular there is no universal Hippocratic randomness test.

Full Text:

10. [PDF]


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Journal of Logic and Analysis ISSN:  1759-9008