0
$\begingroup$

I am working on pseudo random number generation for one of my projects. My goal is to prove that the output is almost Kolmogorov Random since Kolmogorov complexity is uncomputable. So would appreciate any help or guidance for this subject matter.

$\endgroup$
  • $\begingroup$ "Almost Kolmogorov Random" is an interesting concept. Have you ever seen that concept anywhere? If yes, please add a reference. If not, can you raise any idea how to define it reasonably? $\endgroup$ – Apass.Jack Apr 14 at 23:39
  • $\begingroup$ I used that term since KC is not computable. The generate will produce a sequence of pseudo random numbers and I want to analyze it in terms of Kolmogorov randomness. $\endgroup$ – Varun Negandhi Apr 15 at 0:08
  • $\begingroup$ cs.stackexchange.com/questions/69688/… - This link mentions an argument $\endgroup$ – Varun Negandhi Apr 15 at 0:57
  • $\begingroup$ You might think that it could make sense to think in terms of the length of a program to generate the data. Kolmogorov randomness implies that a program to produce the data is longer, so data that could be generated by not-so-long program but not-so-short program would have intermediate Kolmogorov complexity. The problem is that most PRNGs are really short. Even the more complicated non-cryptographically secure PRNGs need only a dozen or so lines of code. That's so they can be fast. I think that some CSPRNGs require more code, but still, the need for speed constrains complexity. $\endgroup$ – Mars May 10 at 3:48
  • $\begingroup$ That link is to a response to a question I asked when I was also confused, and I recommend it. Note that if you could do what you are trying to do in a practical way, it would be a good way to test PRNGs, but instead people use a wide range of statistical tests, as in the TestU01 suite or Dieharder, suggesting that it's not practical. (In a recent book by Diaconis and Skyrms, there's a suggestion that cryptographic PRNGs are kind of analogous to Kolmogorov random, because they are designed to make predicting the sequence computationally difficult. It's not the same thing, though.) $\endgroup$ – Mars May 10 at 3:55
1
$\begingroup$

You can't. Kolmogorov complexity is not computable. See, e.g., https://en.wikipedia.org/wiki/Kolmogorov_complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.