algorithmic incompressibility

Compiled with AI assistance and selectively reviewed. Please consult the cited passages; the books remain the authoritative source. About this companion

Editorial synthesis · provisional

Definition

Algorithmic incompressibility characterizes a string that cannot be generated by a substantially shorter program in the algorithmic-information account presented here. Counting arguments show that most strings of a given length resist such compression. This is a precise account of descriptive randomness, distinct from physical indeterminacy; the corpus also separates a string’s incompressibility from a formal system’s capacity to prove that particular fact.

Explanation

The Chaitin paragraph makes randomness precise through program length, rather than through how surprising, untidy or meaningful a string looks to a human observer. Its counting argument concerns the scarcity of sufficiently short descriptions relative to strings of the specified length. The proposed entry records that local measure without adding a new compression algorithm or claiming every individual string is maximally complex.

The same passage adds a proof limitation: a sound formal system can establish only the specific incompressibility claims permitted by the information content of its axioms. This does not mean that short programs cease to exist when they are unknown, or that a failed search for compression proves incompressibility. The property and an available proof of it are different matters.

The surrounding section explicitly labels the formal results as not ontic indeterminacy, alongside Gödel and Turing’s different limitations. PB similarly separates openness in a formal account from openness in the world. Algorithmic randomness therefore cannot alone certify that a physical generator was indeterministic, that no lawful source existed or that semantic meaning has disappeared.

Scope and attribution

Bound the entry to the algorithmic-information and proof-limit claims actually presented.

RB1 — The Real Book, Volume I: The Possible Is Real

The Chaitin example distinguishes short-program description from what a sound system can prove about particular strings.

Occurrence locators: 129.

Background used in the editorial explanation

Named theories and mechanisms are distinguished from neighboring background, homonyms and the author’s own synthesis. Reproduced AI passages retain their separate voice.