5 ms·
In some sense, the program itself is a ~512 byte compression of an infinite stream of bytes.
by kevinventullo 1y ago
In some sense, the program itself is a ~512 byte compression of an infinite stream of bytes.
- gylterud 1y agoThis is the idea behind Kolmogorov complexity[0], that the complexity of a string (finite or infinite) can be measured, relative to a programming language, as the the length of shortest program which produces it. Precisely computing the Kolmogorov complexity of a given string could be very difficult, though. In general, it is uncomputable because we cannot decide if a given program will output a given string. [0]: https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
- suddenlybananas 1y agoIt's also always relative to some specific programming language, it's not an intrinsic property of strings. (You can of course, convert to another programming language where it's simpler, but then you incur the (constant) cost of the transpiler from language 1 to language 2.)
- gylterud 1y agoAnd by adding a constant to the specification of your programming language, any sequence can have complexity 1! (But of course not every sequence can have its own constant.)