Also interesting is the notion of ‘Kolmogorov Complexity’ - what is the shortest programme that could produce a given output? Worst case for a truly random sequence would just be to copy it out, but a programme that outputs eg. a million digits of pi can actually be quite short. As can a programme that outputs a particular block cypher for an empty input. In general, it is very difficult to decide how long a programme is needed to produce a given output, and what the upper limit of compression could be.
Also interesting is the notion of ‘Kolmogorov Complexity’ - what is the shortest programme that could produce a given output? Worst case for a truly random sequence would just be to copy it out, but a programme that outputs eg. a million digits of pi can actually be quite short. As can a programme that outputs a particular block cypher for an empty input. In general, it is very difficult to decide how long a programme is needed to produce a given output, and what the upper limit of compression could be.
https://en.m.wikipedia.org/wiki/Kolmogorov_complexity