The Randomness Information Paradox

Recovering Information in Complex Systems

Karl Svozil

Technische Universität Wien


To me it has always appeared mind-boggling that the most random sequences, as defined by Algorithmic Information Theory, can carry the most complex messages; messages which contain the highest information content of one per unit of binary code. An example of this kind of property is Chaitin's Omega number, the halting probability that a particular universal computer, when presented prefix-free codes, will halt. Such a sequence contains all formalizable mathematical truth that can be expressed as a halting decision problem. Another complex behavior similar to Omega emerges in the physical problem of the movement of N bodies: although in principle solvable by power series solutions, those series might not have a computable radius of convergence.

Of course, there exist two sides of the same coin: encrypting complexity in random sequences on the one hand, and deciphering, decrypting those messages on the other hand. While it appears evident that regular-looking, monotonous sequences contain less complexity, it is by no means trivial to recover the information contained in very complex, random sequences. In general, due to reduction to the halting problem, this task is impossibly provable.

These problems persist not only in the formalized sciences. Every work of art can be seen as a complex structure created by the artist and needing decryption and understanding from the audience. Thus human aesthetics can be developed as a function of decryption. Decryption is analyzed in terms of computation, thus providing some principles by which artists may design appealing designs. While too condensed coding makes decryption of a work of art impossible and is perceived as random and chaotic by the untrained mind, too regular structures are perceived as monotonous, too orderly and not very stimulating. It is also argued that, due to human predisposition, aesthetics is inevitably based on natural forms. And it is interesting to note that different forms of contemporary art have developed differently: wherever the costs of complexity are relatively low, such as in music or painting, the complexity increased, resulting in random, incomprehensive creations whose comprehension requires repetition and effort. Whenever the expenses are high, such as in architecture and still even in virtual space, the complexity has decreased or remains low, mostly connected to the pressure of cost and the scarcity of resources.