3 ms·

I find it's often more useful to replace the "random" property of an object with the "incapable of predicting" property of the observer/consumer/receiver/attack

I find it's often more useful to replace the "random" property of an object with the "incapable of predicting" property of the observer/consumer/receiver/attacker/whatever. This is basically the approach taken by information theory: one of Shannon's many insights is that the content of a message doesn't matter for communicating it; only how well the receiver can predict it. If there are two possible messages, it doesn't matter if they're "yes"/"no" or "invade Portugal"/"bring me a sandwich", the information being communicated is the same (1 bit). In this way, something is "random" if it's maximally unpredictable, i.e. if it can't be compressed. If we pick a Universal Turing Machine as the receiver, we get the characterisation of randomness given by Kolmogorov complexity.

marxidad 10y ago
From https://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness https://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogor... : Kolmogorov randomness defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string. To make this precise, a universal computer (or universal Turing machine) must be specified, so that "program" means a program for this universal machine. A random string in this sense is "incompressible" in that it is impossible to "compress" the string into a program whose length is shorter than the length of the string itself. A counting argument is used to show that, for any universal computer, there is at least one algorithmically random string of each length. Whether any particular string is random, however, depends on the specific universal computer that is chosen.