How does algorithmic information theory measure the complexity of a message?
Consider a simple telephone conversation: A person (message source) speaks into a telephone receiver (encoder), which converts the sound of the spoken word into an electrical signal. This electrical signal is then transmitted over telephone lines (channel) subject to interference (noise). When the signal reaches the telephone receiver (decoder) at the other end of the line it is converted back into vocal sounds. Finally, the recipient (message receiver) hears the original message.
In algorithmic information theory (AIT), the complexity of a message is defined as the length of the shortest algorithm—or step-by-step procedure—required to reproduce that message.1
This approach, developed in the 1960s by mathematicians Gregory Chaitin, Andrey Kolmogorov, and engineer Raymond Solomonoff, provides an objective measure of a message's intrinsic complexity. By focusing on the minimum computational instructions needed to generate a specific output, AIT distinguishes itself from classical information theory, which primarily addresses the technical problems of transmitting signals over communication channels.12