Hacker News Reader

In some sense, the program itself is a ~512 byte compression of an infinite stream of bytes.

This 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

It'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.)

And 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.)

Reply on news.ycombinator.com