STRATA
Skip to study
XLVII

I.07 / GNOSIS

Algorithmic information and Kolmogorov complexity

How short a description will reproduce a sequence, and how does the choice of description language change that estimate?

A source-led introduction1 source references1 related experiments

Start with the question.

Algorithmic information asks how briefly an individual object can be described by a program in a specified computational language. Vitányi's account makes the incomputability issue central: a compressor's output is a practical description, while the shortest possible description is a different mathematical object. This distinction lets compression remain useful without treating a file-size comparison as an exact measurement of intrinsic complexity.

Separate repetition from a compressor's overhead.

Compare a thousand repeated characters, a repeated sentence, and a fixed pseudorandom sequence using the same compressor and settings. Record both input and output byte counts. Repeat with very short files, where headers can outweigh any saving; a larger compressed file can then reflect format overhead rather than deeper structure.

What would you inspect?

  • Compressor name, version, settings, and any shared dictionary.
  • The change in measured length when file size or encoding changes.

Take the next step.

Reproduce one compression comparison with two algorithms and explain which conclusion survives the change in representation.

Put part of the question to work.

These models isolate a mechanism you can vary. Their assumptions define the part of this topic they can illuminate.

Try entropy and compression.

Change one parameter, compare the numerical output, and export the result. The experiment loads when you open it.

Open its full page

Watch the quantities change.

12 seconds · Original model visualization · Silent

Entropy and compression

Compare symbol frequencies with the ordering that a code can exploit.

Read the explanation and method

The first sweep changes the probability of A while drawing each symbol independently. The other three symbols share the remaining probability.

As one symbol dominates, the observed symbol entropy falls. Huffman codes use short words for frequent symbols; the comparison excludes headers and the codebook.

The second sweep gives all four new draws equal probability and increases repetition. Long runs reward run-length coding, even when a symbol histogram cannot describe the dependence.

Method. The histogram gives an order-zero Shannon entropy. Huffman coding repeatedly joins the two least frequent branches to build a prefix code. The run-length format stores a two-bit symbol and an eight-bit count; counts run from 1 to 255, and a longer run uses another packet.

Read the supporting material.

  1. How incomputable is Kolmogorov complexity?

    Paul M. B. Vitányi / arXiv · Formal complexity and limits of computing shortest descriptions; practical compressors are distinct objects.

Follow the comparisons.

Read the neighboring questions.