MachuPikacchu on Nostr: In other words, “true randomness” is relative to the observer. There’s a ...

In other words, “true randomness” is relative to the observer. There’s a continuum between cryptographically secure randomness and “true” randomness. True randomness occurs when the Kolmogorov complexity [1] of the random process exceeds the maximum possible computational budget of the observer while cryptographically secure randomness occurs when the complexity exceeds the observer’s budget on a sufficiently long time scale.

1. https://en.m.wikipedia.org/wiki/Kolmogorov_complexity

quoting note19mv…3as8

Some thoughts on randomness and how it relates to computation.

Computation is the act of following rules to transform inputs into outputs.

Computational irreducibility is the idea that for some systems the output can’t be predicted from the input without performing the computation. For example the SHA256 of a string is deterministic and computable (therefore the output is not truly random) but there are no shortcuts for getting the output aside from doing all the steps.

The path a ball takes when you throw it on the other hand is computationally reducible since we have equations of motion and can predict where it goes before throwing it.

Computational irreducibility is a necessary component of true randomness but it’s not sufficient.
So then what does it mean to be truly random? In this context my best guess is that it’s a process whose compute requirements exceed what’s available to the observer. The observer (the person or system interacting with the “random” process) can’t run the algorithm needed to produce the apparent randomness.

Example: suppose you have a computer with only 7 bytes of memory. You can’t perform SHA256 since you need at least 8 bytes of memory for the registers alone and you obviously need a budget for storing the algorithm itself. The output of SHA256 would be forever appear random to your computer.