Is the Library of Babel random? Does it contain information?

Question

The Library of Babel is defined as

a universe in the form of a vast library containing all possible 410-page books of a certain format and character set.

However, applying two means of randomness/information measurement to the system produces different outputs.

The library clearly has a very high Shannon entropy, which suggests it contains information and is random.

However, the library has a very low Kolmogorov complexity when read identically to the first, since it can be generated by a simple program iterating over all the possible characters in the set. This suggests it is not random.

Which of these interpretations better describes the library?

Answer 1

I think the issue is that while the Shannon entropy could be considered an "objective" property of the library, the "algorithmic complexity" of the program required to generate the content of the library is not an objective property, but depends on the specifics of the Turing machine available.

Since the library has a finite number of unique texts within it, it's trivially easy to design a Turing machine that generates the entire unique content of the library in $O(1)$ - simply hardwire the whole content into the "instruction set architecture" of the machine. But you can imagine other types of very limited Turing machines where the "simple program" you describe to generate the library might not be so simple at all.

The purportedly objective characterization of the complexity/randomness of a single string of symbols given by algorithmic information theory turns out to be objective only insofar as one specifies a Turing machine. Algorithmic complexity simpliciter is no more an objective property of a string than velocity is an objective property of a physical object.

See this paper for more details: Objectivity, Information, and Maxwell's Demon