How much information is in a single grain of sand? Or in the novel Moby Dick? Or in a 30-second pop song? These questions seem impossible to answer. Information theory, as it was originally conceived, couldn't help. It was designed to measure the average information produced by a source, like a telegraph line sending messages. It tells you about the channel, not the individual message.

Algorithmic Information Theory (AIT) takes a completely different approach. It provides a way to measure the information content, or complexity, of a single, specific object. The core idea is surprisingly simple: the amount of information in an object is the length of the shortest possible set of instructions to create it.

This definition is powerful, but it raises a question. The length of a program depends on the programming language and the computer you use. A program written in Python might be shorter than one in Assembly. To make this a universal measure, we need a universal standard for a computer.

Computer scientists solved this problem decades ago with a theoretical model called a Universal Turing Machine (UTM). You can think of a UTM as a bare-bones, idealized computer. It has a tape (memory), a head that can read and write symbols on the tape, and a simple set of rules it follows.

What makes it "universal" is that it can be programmed to simulate any other computer. Given the right instructions, a UTM can run a Python program, a video game, or the operating system of your phone. By agreeing to measure our program lengths on a standard UTM, we can create a consistent, objective measure of information content. The choice of UTM doesn't significantly change the relative information content of objects; the shortest program for one UTM will be roughly the same length as for another.

So, how does this algorithmic information differ from the classical information theory developed by Claude Shannon? The distinction is fundamental. Shannon's theory is about probability and averages. It measures how much surprise or uncertainty is reduced when you receive a message from a known source.

Algorithmic information theory isn't concerned with probability or sources. It focuses on the object itself and its internal structure. A complex, random-looking string is considered to have more information than a simple, patterned one, regardless of how they were generated.

Let's consider two 32-bit strings.

String A is 01010101010101010101010101010101. It's highly ordered. A short program can describe it perfectly:

String B is 11010010001011010110011011101011. It looks random. There's no obvious pattern. The shortest way to describe this string is likely just to state the string itself.

In classical information theory, if each bit (0 or 1) has an equal chance of appearing, both strings contain 32 bits of information. But in AIT, String A has very low information content because its description is short. String B has high information content because it's incompressible; its shortest description is the string itself.

This idea of measuring the length of the shortest program gives us a formal way to talk about complexity and randomness. The concept is known as Kolmogorov complexity, which builds directly on these foundations.