42.04.08 · mathematical-logic / computability-degrees

Kolmogorov Complexity and Algorithmic Randomness

shipped3 tiersLean: none

Anchor (Master): Downey and Hirschfeldt 2010 *Algorithmic Randomness and Complexity* (Springer) Ch. 6-11 (the Schnorr-Levin characterisation, Chaitin's $\Omega$ as a left-c.e. ML-random real, van Lambalgen's theorem, the randomness hierarchy — computable, Schnorr, ML, weak-2, and 2-randomness — and the degree theory of randomness: $K$-lowness, lowness for ML-randomness, the Nies-Hirschfeldt-Downey theorem that low-for-random $=$ low-for-$K$ $=$ $K$-low, and the relation to the c.e. and Turing degrees); Nies 2009 *Computability and Randomness* (Oxford Logic Guides 51) Ch. 3, 5, 8 (the prefix-free machine theory, ML-randomness and its degree theory, the $K$-low reals and the cost-function method); Li and Vitányi 2019 *An Introduction to Kolmogorov Complexity and Its Applications* 4e (Springer) Ch. 2-4, 6 for the incompressibility method in combinatorics and average-case analysis

Intuition Beginner

The earlier units in this chapter measured how hard a set is to compute. This unit measures something that sounds different but turns out to be the same story told backwards: how random a string or a sequence is. The link is a single idea — randomness is the absence of any pattern a computer could exploit.

Think about describing a string of a thousand digits to a friend over the phone. If the string is "one thousand zeros," you say exactly that, and the description is tiny. If the string is the first thousand digits of a familiar constant, you name the constant. But if the string was made by flipping a fair coin a thousand times, there is almost certainly no short way to say it: the shortest description is roughly the string itself, digit for digit. The length of the shortest description is a measure of how much real information the string carries.

Call a string incompressible when its shortest description is about as long as the string. Most strings are incompressible, for a plain counting reason: there are far more long strings than there are short descriptions to go around, so short descriptions run out and most strings are stuck describing themselves. Incompressible is the finite version of random.

For infinite sequences the same instinct needs a second sharpening. A sequence is random when it passes every test a computer could run to catch a pattern — every effective bet, every effective regularity, every shrinking target a program could aim at. Remarkably, three different ways of saying "no pattern" — passing every effective test, having incompressible chunks, and avoiding every small effectively-described target — all pick out the very same sequences. And there is a single most famous random number, built straight from the halting problem, called Chaitin's number. The rest of the unit makes the three pictures precise and proves they coincide.

Visual Beginner

Picture every length- $n$ string on the left and every shorter program on the right, and try to pair each string with a program that prints it.

   strings of length n            programs shorter than n
   (there are 2^n of them)        (there are 2^n - 1 of them)

   000...0  --------------------> "n zeros"        (a short program)
   a familiar pattern  ---------> "the pattern"    (a short program)
   ...
   most strings  ----- ? -------> NOT ENOUGH short programs left
                                  -> the string must describe itself

   Count: 2^n strings, only 2^n - 1 shorter programs.
   The short programs run out, so most strings are INCOMPRESSIBLE.

Now the infinite picture. A test is a shrinking sequence of targets a computer can list, with the targets getting smaller and smaller; a sequence is caught if it lands in every target.

picture of "random"	what the computer does	a sequence is random when
incompressible chunks	compress each starting block	no block compresses by more than a fixed amount
passes every test	list shrinking targets to catch patterns	it escapes every shrinking target
avoids small targets	aim at effectively-described tiny regions	it sits in no effectively-tiny region

Read the table across: three different machines, three different verdicts, but they agree on exactly which sequences count as random. The agreement is the heart of the subject.

Worked example Beginner

We compare three length-eight strings and read off how compressible each is, to feel the difference between order and randomness with concrete numbers.

Step 1. Take $00000000$ . A description is "print $0$ eight times," which is far shorter than the string itself once the count gets large; the content is just the pair "the symbol $0$ " and "the number $8$ ." This string is highly compressible — almost all of its eight bits are predictable from a short recipe.

Step 2. Take $01010101$ . A description is "print $01$ four times." Again the recipe is short: one small block plus a repeat count. Compressible, for the same reason — a rule generates the whole string, so you ship the rule, not the string.

Step 3. Take $01101000$ , produced by eight coin flips. There is no shorter rule in sight: "print $01101000$ " is about the best you can do, so the description is roughly the string itself. Among the $256$ strings of length eight, at most $255$ can have a description shorter than eight bits, because there are only $255$ programs of length seven or less. So at least one string of length eight is incompressible, and in fact the large majority are within a bit or two of incompressible.

What this tells us: compressibility tracks pattern. A string with a rule behind it has a short description; a string made at random almost surely has none, because short descriptions are a scarce resource that the many random strings cannot all share. The same scarcity, pushed to infinite sequences, is what makes "random" mean "no effective pattern, anywhere, ever."

Check your understanding Beginner

Formal definition Intermediate+

Fix the standard enumeration ${φ_{e}}$ , the c.e. sets $W_{e}$ with stage approximations of 42.04.03, oracle functionals $Φ_{e}^{A}$ , the jump $A^{'}$ , and the iterated jumps $\emptyset^{(n)}$ of 42.04.04. Strings are elements of $2^{< ω}$ , sequences elements of Cantor space $2^{ω}$ with the uniform (Lebesgue) measure $μ$ ; $X ↾ n$ is the length- $n$ prefix of $X$ , and $[σ] = {X : σ ≺ X}$ is the basic clopen cylinder, $μ ([σ]) = 2^{- ∣ σ ∣}$ .

A machine is a partial computable $M : 2^{< ω} \to 2^{< ω}$ . The plain complexity relative to $M$ is $C_{M} (x) = min {∣ p ∣ : M (p) = x}$ ( $\infty$ if none). A machine $U$ is universal if for every $M$ there is a constant $c_{M}$ with $C_{U} (x) \leq C_{M} (x) + c_{M}$ for all $x$ ; the invariance theorem gives such a $U$ , and any two universal machines agree up to an additive constant, so $C := C_{U}$ is well-defined modulo $O (1)$ ^{[Li-Vitanyi Ch. 2]}. A machine $M$ is prefix-free if its domain is an antichain under $≺$ (no halting program is a prefix of another). A universal prefix-free machine exists by the same argument; its complexity is the prefix (Kolmogorov-Chaitin) complexity $K (x) = min {∣ p ∣ : U (p) = x, U prefix-free}$ , again well-defined up to $O (1)$ . The defining inequalities are $C (x) \leq K (x) + O (1)$ and $K (x) \leq C (x) + 2 lo g C (x) + O (1)$ .

A prefix-free machine's domain $D$ satisfies the Kraft inequality $\sum_{p \in D} 2^{- ∣ p ∣} \leq 1$ . Conversely, the Kraft-Chaitin theorem: given a c.e. set of requests $(ℓ_{i}, x_{i})$ with $\sum_{i} 2^{- ℓ_{i}} \leq 1$ , there is a prefix-free machine $M$ and, for each request, a program $p_{i}$ with $∣ p_{i} ∣ = ℓ_{i}$ and $M (p_{i}) = x_{i}$ . Hence $K$ is subadditive, $K (⟨ x, y ⟩) \leq K (x) + K (y) + O (1)$ , repairing the failure of subadditivity for $C$ ^{[Nies Ch. 2]}.

A Martin-Löf test is a uniformly c.e. sequence $(U_{n})_{n \in ω}$ of $Σ_{1}^{0}$ classes in $2^{ω}$ with $μ (U_{n}) \leq 2^{- n}$ . A sequence $X$ fails the test if $X \in ⋂_{n} U_{n}$ ; the failure set is an effective null set. $X$ is Martin-Löf random (ML-random) if it fails no ML-test, equivalently passes a single universal ML-test $(U_{n})$ obtained by effectively combining all tests ^{[Downey-Hirschfeldt Ch. 6]}. A real $α \in [0, 1]$ is left-c.e. if it is the increasing limit of a computable sequence of rationals.

A set $A$ is $K$ -low if $K (A ↾ n) \leq K (n) + O (1)$ for all $n$ . A set $A$ is low for ML-randomness if every ML-random sequence is ML-random relative to $A$ , and low for $K$ if $K^{A} (x) \geq K (x) - O (1)$ for all $x$ .

Counterexamples to common slips Intermediate+

"Plain complexity $C$ is subadditive." It is not: $C (⟨ x, y ⟩) \leq C (x) + C (y) + O (1)$ fails because a plain decoder cannot tell where the program for $x$ ends and that for $y$ begins. The self-delimiting prefix-free domain is precisely what restores $\sum 2^{- ∣ p ∣} \leq 1$ and hence $K (⟨ x, y ⟩) \leq K (x) + K (y) + O (1)$ .
" $K (X ↾ n) \geq n$ characterises ML-randomness." The exact bound must absorb an additive constant: ML-randomness is $K (X ↾ n) \geq n - O (1)$ . With plain $C$ even $C (X ↾ n) \geq n - O (1)$ fails for every $X$ — complexity oscillations force $C (X ↾ n) \leq n - lo g n$ infinitely often, which is why the Schnorr-Levin theorem uses $K$ , not $C$ .
"Random means avoiding every measure-zero set." Only the effective null sets count. A single ML-random $X$ is the sole member of the measure-zero set ${X}$ , which it certainly does not avoid; the constraint is to avoid every effectively-presented (uniformly c.e., measure-controlled) null set, of which there are only countably many.
" $Ω$ depends on nothing but the definition." $Ω$ depends on the choice of universal prefix machine $U$ ; different $U$ give different reals. What is invariant is that every such $Ω$ is left-c.e., ML-random, and Turing-equivalent to $\emptyset^{'}$ ; the Solovay-complete left-c.e. reals are exactly these halting probabilities (Kučera-Slaman).

Key theorem with proof Intermediate+

The organising result identifies randomness with incompressibility: a sequence is Martin-Löf random exactly when no initial segment can be compressed by more than a constant. This is the Schnorr-Levin theorem, and it ties the test picture to the complexity picture.

Theorem (Schnorr-Levin). For $X \in 2^{ω}$ : $X$ is Martin-Löf random iff there is a constant $c$ with $K (X ↾ n) \geq n - c$ for all $n$ . ^{[Downey-Hirschfeldt Ch. 6]}

Proof. ( $\Leftarrow$ by contraposition: not ML-random $\Rightarrow$ initial segments compressible.) Suppose $X$ fails the universal ML-test $(U_{n})$ , so $X \in ⋂_{n} U_{n}$ with $μ (U_{n}) \leq 2^{- n}$ . Each $U_{n}$ is $Σ_{1}^{0}$ , hence a c.e. union of cylinders $[σ]$ ; list for each $n$ the strings $σ$ generating $U_{n}$ . For the level $U_{2 d}$ ( $μ \leq 2^{- 2 d}$ ), the generating strings $σ$ satisfy $\sum_{σ} 2^{- ∣ σ ∣} \leq 2^{- 2 d}$ , so $\sum_{σ} 2^{- (∣ σ ∣ - d)} \leq 2^{- d}$ and summing over $d$ keeps the total $\leq 1$ . By the Kraft-Chaitin theorem build a prefix machine that, on a program of length $∣ σ ∣ - d$ , outputs $σ$ ; then $K (σ) \leq ∣ σ ∣ - d + O (1)$ for every $σ$ generating $U_{2 d}$ . Since $X \in U_{2 d}$ for every $d$ , some prefix $σ = X ↾ m$ generates it, giving $K (X ↾ m) \leq m - d + O (1)$ . As $d$ grows, the compression $d$ is unbounded, so $K (X ↾ n) \geq n - c$ fails for every $c$ .

( $\Rightarrow$ by contraposition: compressible initial segments $\Rightarrow$ not ML-random.) Suppose for every $c$ there is $n$ with $K (X ↾ n) < n - c$ . Define $V_{c} = ⋃ {[τ] : ∣ τ ∣ = n, K (τ) < n - c for some n}$ , a $Σ_{1}^{0}$ class since $K$ is upper-semicomputable (its graph is c.e. from above). Counting: the number of strings $τ$ of length $n$ with $K (τ) < n - c$ is at most the number of prefix programs of length $< n - c$ , and by the Kraft inequality $\sum_{τ : K (τ) < n - c} 2^{- ∣ τ ∣} \leq \sum_{∣ p ∣ < n - c} 2^{- (∣ p ∣ + c)} \leq 2^{- c}$ ; summing the measure over all such $τ$ gives $μ (V_{c}) \leq 2^{- c}$ . So $(V_{c})_{c}$ is an ML-test (after the index shift $c \mapsto$ level), and $X \in ⋂_{c} V_{c}$ because some initial segment of $X$ enters each $V_{c}$ . Thus $X$ fails an ML-test and is not ML-random. $□$

Bridge. The Schnorr-Levin theorem is the foundational reason the two definitions of randomness — passing every effective test and having incompressible initial segments — are not two notions but one: a test of measure $\leq 2^{- d}$ is, via Kraft-Chaitin, a $d$ -bit compression of whatever it catches, and incompressibility is exactly the absence of every such compression. This is exactly the counting argument of the Beginner tier made effective, where short descriptions are scarce and a measure- $2^{- d}$ target is a description $d$ bits shorter than the string it traps; the Kraft inequality is the conservation law that bounds how many strings can be cheaply described, and it is dual to the measure bound on tests. The construction builds toward Chaitin's $Ω$ in the Advanced results, the canonical sequence whose initial segments are incompressible because $Ω$ is the halting probability of the very prefix machine defining $K$ , and it appears again in van Lambalgen's theorem, where relativised incompressibility makes randomness a symmetric relation. The central insight is that the jump of 42.04.04 enters here as the source of the canonical random real: $Ω \equiv_{T} \emptyset^{'}$ , so the halting problem is not merely hard but maximally information-dense, and putting these together, randomness measured by tests, by $K$ , and by effective null sets is one phenomenon whose canonical witness is built from $\emptyset^{'}$ .

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the incompressibility theorem: for every $n$ there is a string $x$ of length $n$ with $C (x) \geq n$ , and at least $2^{n} (1 - 2^{- c})$ strings of length $n$ with $C (x) \geq n - c$ .

Hint

Count the programs of length $< n - c$ and compare with the $2^{n}$ strings.

Answer

The number of programs of length $< k$ is $2^{k} - 1 < 2^{k}$ . A string $x$ with $C (x) < n - c$ has a program of length $< n - c$ , and the map "program $\mapsto$ its output" is a function, so at most $2^{n - c} - 1 < 2^{n - c}$ strings of length $n$ have $C (x) < n - c$ . Hence at least $2^{n} - 2^{n - c} = 2^{n} (1 - 2^{- c})$ strings of length $n$ satisfy $C (x) \geq n - c$ . Taking $c = 0$ : at most $2^{n} - 1$ strings of length $n$ have $C (x) < n$ , so at least one has $C (x) \geq n$ . Rubric: full credit for the program-count bound $< 2^{n - c}$ , the function (at-most-one-output) observation, and the subtraction giving the proportion $1 - 2^{- c}$ .

Exercise 4 (medium, symbolic).

Prove that $C$ is not computable, using Berry's paradox: if $C$ were computable, "the least string $x$ with $C (x) > n$ " would have a short description.

Hint

Such a string exists for each $n$ by the incompressibility theorem; describe it by $n$ plus a fixed program.

Answer

Suppose $C$ is computable. Define $f (n) =$ the lexicographically least string $x$ with $C (x) > n$ ; by the incompressibility theorem such $x$ exists (strings of length $n + 1$ include one with $C \geq n + 1 > n$ ), and with $C$ computable $f$ is computable by search. Now $f (n)$ has a description: a fixed program for $f$ together with $n$ in binary, of total length $∣ f ’s program ∣ + lo g n + O (1) = lo g n + O (1)$ . So $C (f (n)) \leq lo g n + O (1)$ . But by definition $C (f (n)) > n$ . For large $n$ , $lo g n + O (1) < n$ , contradiction. Hence $C$ is not computable. (It remains upper-semicomputable: $C (x) \leq k$ is c.e., by dovetailing all programs of length $\leq k$ .) Rubric: full credit for defining $f$ via the incompressibility theorem, bounding $C (f (n)) \leq lo g n + O (1)$ from the short description, and contradicting $C (f (n)) > n$ .

Exercise 6 (hard, symbolic).

Prove that Chaitin's $Ω$ is Martin-Löf random, using the Schnorr-Levin theorem and the fact that the first $n$ bits of $Ω$ determine which programs of length $\leq n$ halt.

Hint

From $Ω ↾ n$ you can compute the halting set restricted to programs of length $\leq n$ , hence recover any short string those programs output.

Answer

Write $Ω_{s}$ for the stage- $s$ lower approximation, increasing to $Ω$ . Given the first $n$ bits of $Ω$ , run the enumeration until $Ω_{s}$ first exceeds $Ω ↾ n$ (as a binary fraction); at that stage every program $p$ with $∣ p ∣ \leq n$ that will ever halt has already halted, since any later halting program would add $\geq 2^{- n}$ and push $Ω$ past $Ω ↾ n + 2^{- n}$ , contradicting the known first $n$ bits. So from $Ω ↾ n$ one computes the finite set $H_{n}$ of halting programs of length $\leq n$ and all their outputs. Now suppose $K (Ω ↾ n) < n - c$ for some $n$ and a would-be unbounded $c$ : a prefix program $q$ of length $< n - c$ produces $Ω ↾ n$ , from which $H_{n}$ and the outputs of all length- $\leq n$ programs are computable. Diagonalising — output a string of complexity $> n$ using the recovered $H_{n}$ — yields a string described by $q$ plus $O (1)$ bits, of length $< n - c + O (1) < n$ , yet of complexity $> n$ , a contradiction once $c$ exceeds the fixed overhead. Hence $K (Ω ↾ n) \geq n - O (1)$ for all $n$ , and by Schnorr-Levin $Ω$ is ML-random. Rubric: full credit for recovering $H_{n}$ from $Ω ↾ n$ via the approximation-overshoot argument, the diagonal extraction of a high-complexity string from a short description of $Ω ↾ n$ , and the appeal to Schnorr-Levin.

Exercise 7 (hard, symbolic).

State and prove van Lambalgen's theorem in the easy direction: if $X \oplus Y$ is ML-random then $X$ is ML-random and $Y$ is ML-random relative to $X$ .

Hint

A test for $X$ alone, or a test for $Y$ relative to $X$ , lifts to a test for the join $X \oplus Y$ of the same measure.

Answer

Recall $X \oplus Y$ interleaves the two sequences. ( $X$ random.) If $X$ failed an ML-test $(U_{n})$ , then $V_{n} = {Z \oplus W : Z \in U_{n}, W \in 2^{ω}}$ is a uniformly c.e. sequence of $Σ_{1}^{0}$ classes with $μ (V_{n}) = μ (U_{n}) \leq 2^{- n}$ (the $W$ -coordinate is free, measure $1$ ), and $X \oplus Y \in ⋂_{n} V_{n}$ , so $X \oplus Y$ fails an ML-test — contradiction. Hence $X$ is ML-random. ( $Y$ random relative to $X$ .) Suppose $Y$ failed an $X$ -ML-test $(U_{n}^{X})$ , with $U_{n}^{X}$ uniformly $Σ_{1}^{0, X}$ and $μ (U_{n}^{X}) \leq 2^{- n}$ . By Fubini, integrate over the $X$ -coordinate: the set $W_{n} = {Z \oplus W : W \in U_{n}^{Z}}$ is $Σ_{1}^{0}$ (the oracle $Z$ is read from the even coordinates of the join) with $μ (W_{n}) = \int μ (U_{n}^{Z}) d Z \leq 2^{- n}$ , and $X \oplus Y \in ⋂_{n} W_{n}$ since $Y \in U_{n}^{X}$ for all $n$ . So $X \oplus Y$ fails an ML-test, contradicting its randomness. Therefore $Y$ is ML-random relative to $X$ . Rubric: full credit for lifting an $X$ -test to a join-test with the free $W$ -coordinate, the Fubini measure bound for the relativised test, and the contradiction with randomness of $X \oplus Y$ in both parts.

Advanced results Master

Randomness has a degree theory as rich as the c.e. degrees of 42.04.06: the maximally non-random reals form a definable ideal, the canonical random real is the halting probability, and the randomness notions stratify into a strict hierarchy indexed by the jump.

Theorem 1 (Chaitin's $Ω$ ; the number of wisdom). Fix a universal prefix machine $U$ and set $Ω = \sum_{U (p) ↓} 2^{- ∣ p ∣}$ , the halting probability ^{[Downey-Hirschfeldt Ch. 6]}. Then $Ω \in (0, 1)$ is left-c.e. (the increasing limit $Ω_{s} = \sum_{U_{s} (p) ↓} 2^{- ∣ p ∣}$ of computable rationals), Martin-Löf random (its initial segments are incompressible, by Schnorr-Levin), and incomputable; moreover $Ω \equiv_{T} \emptyset^{'}$ , and the first $n$ bits of $Ω$ uniformly compute the halting of all programs of length $\leq n$ . The left-c.e. ML-random reals are exactly the $Ω$ -numbers — the halting probabilities of universal prefix machines — and they are precisely the Solovay-complete c.e. reals (Calude-Hertling-Khoussainov-Wang; Kučera-Slaman). Thus $Ω$ packages the entire halting problem into a single real that is simultaneously as enumerable as a c.e. set and as patternless as a fair coin.

Theorem 2 ( $K$ -lowness and lowness coincide). A set $A$ is $K$ -low if $K (A ↾ n) \leq K (n) + O (1)$ : its initial segments are as compressible as possible, the exact antithesis of $Ω$ . The Nies-Hirschfeldt-Downey theorem ^{[Nies Ch. 5]} identifies three a priori different lowness notions: $A$ is $K$ -low $⟺$ $A$ is low for $K$ ( $K^{A} = K + O (1)$ ) $⟺$ $A$ is low for ML-randomness (every ML-random real stays ML-random relative to $A$ ) $⟺$ $A$ is a base for ML-randomness ( $A \leq_{T} Z$ for some $Z$ that is ML-random relative to $A$ ). Every $K$ -low set is $Δ_{2}^{0}$ , and the $K$ -lows form a $Σ_{3}^{0}$ , c.e.-presentable, downward-closed ideal under $\oplus$ in the Turing degrees, lying strictly below $\emptyset^{'}$ , inside both the low degrees ( $A^{'} \equiv_{T} \emptyset^{'}$ ) and the non-cuppable c.e. degrees. There are noncomputable $K$ -lows (Solovay; Downey-Hirschfeldt-Nies-Stephan), built by the cost-function method.

Theorem 3 (van Lambalgen's theorem). $X \oplus Y$ is ML-random iff $X$ is ML-random and $Y$ is ML-random relative to $X$ ^{[Nies Ch. 3]}. Consequently relative randomness is symmetric for ML-random reals: if $X \oplus Y$ is random then $X$ is random relative to $Y$ and $Y$ random relative to $X$ , so " $X$ is random relative to $Y$ " and " $Y$ is random relative to $X$ " hold together. The theorem is the engine of the degree theory of randomness — it reduces questions about pairs to relativised single-real questions, and it fails for the weaker notions (Schnorr, computable randomness), which is one diagnostic separating ML-randomness from its neighbours.

Theorem 4 (the randomness hierarchy). The natural randomness notions form a strict ascending chain ^{[Downey-Hirschfeldt Ch. 7]}: computable randomness $⊋$ Schnorr randomness at the lower end, then Martin-Löf randomness, weak-2-randomness, and $n$ -randomness ( $=$ ML-randomness relative to $\emptyset^{(n - 1)}$ ), with each notion strictly stronger than the last and $2$ -randomness already strong enough to make $X^{'} \equiv_{T} X \oplus \emptyset^{'}$ (the random real adds no jump information beyond the join). Schnorr randomness uses tests whose measures converge computably to $0$ ; weak-2-randomness uses $Π_{2}^{0}$ null sets; the $n$ -randomness ladder is the arithmetical hierarchy of 42.04.05 applied to the test complexity, so the jump of 42.04.04 indexes the strength of randomness exactly as it indexes computational difficulty. The Kučera-Gács theorem sits across this picture: every real is computable from some ML-random real, so randomness does not bound Turing complexity from above.

Theorem 5 (the incompressibility method and normality). Algorithmic randomness yields a proof technique — the incompressibility method ^{[Li-Vitanyi Ch. 6]}: to prove a combinatorial statement, fix an incompressible object (a string $x$ with $C (x) \geq ∣ x ∣$ ) and derive bounds from the impossibility of compressing it. It delivers average-case lower bounds for sorting and Turing-machine running time, the expected $O (n lo g n)$ behaviour of algorithms, Ramsey-type and graph estimates, and number-theoretic bounds (including prime-gap estimates), serving as a deterministic counterpart of the probabilistic method, with the incompressible object playing the role of the "random" object whose existence the counting argument guarantees. Algorithmic randomness also refines classical typicality: every ML-random sequence is Borel-normal (each block of digits appears with its limiting frequency), but normality is strictly weaker — there are computable normal numbers (Champernowne's constant) that are far from random.

Synthesis. Algorithmic randomness is the foundational reason "no pattern" has a single precise meaning rather than three competing ones: unpredictability by effective tests, incompressibility by prefix complexity, and avoidance of every effective null set are the same condition, and this is exactly the Schnorr-Levin theorem read together with the universal-test construction — a measure- $2^{- d}$ effective target is, via Kraft-Chaitin, a $d$ -bit compression, so a test is a description and incompressibility is the absence of descriptions. The canonical witness is Chaitin's $Ω$ , the halting probability of the prefix machine that defines $K$ , which is left-c.e. like a c.e. set yet ML-random like a fair coin and Turing-equivalent to $\emptyset^{'}$ ; this is the central insight that the halting problem of 42.04.02 is not merely undecidable but maximally information-dense, and it generalises the jump of 42.04.04 from a measure of difficulty to a source of randomness.

The degree theory mirrors the c.e. degrees of 42.04.06 in negative: where the priority method populates the interval $(0, 0^{'})$ with intermediate degrees, the $K$ -lows populate it with the least random reals, and the Nies-Hirschfeldt-Downey coincidence — $K$ -low $=$ low for $K$ $=$ low for ML-random — makes "adds no randomness power" a single robust class, a $Σ_{3}^{0}$ ideal of low non-cuppable degrees dual to $Ω$ at the random extreme. Putting these together, the randomness hierarchy is the arithmetical hierarchy of 42.04.05 applied to test complexity: $n$ -randomness is randomness relative to $\emptyset^{(n - 1)}$ , so the iterated jump indexes both ladders, and van Lambalgen's theorem is the bridge that makes relativised randomness symmetric, the foundational reason a degree theory of randomness exists at all. The incompressibility method then turns the whole apparatus outward, using a single incompressible object as the deterministic stand-in for the probabilistic method across combinatorics and average-case analysis.

Full proof set Master

Proposition 1 (invariance theorem). There is a universal prefix-free machine $U$ such that for every prefix-free machine $M$ there is $c_{M}$ with $K (x) \leq C_{M} (x) + c_{M}$ for all $x$ ; consequently any two universal prefix-free machines give complexities agreeing within $O (1)$ .

Proof. Enumerate the prefix-free machines $M_{0}, M_{1}, \dots$ uniformly (effectively recognising prefix-freeness is not needed: clip each machine to its prefix-free core by accepting a program only if no proper prefix has already halted, which preserves universality). Fix a prefix-free coding $e \mapsto \overset{e}{ˉ}$ of indices with $∣ \overset{e}{ˉ} ∣ = O (1) + 2 lo g e$ — itself prefix-free since the codes form an antichain. Define $U (\overset{e}{ˉ} p) = M_{e} (p)$ ; the domain is prefix-free because $\overset{e}{ˉ}$ is self-delimiting and each $M_{e}$ has prefix-free domain, so no halting input of $U$ is a prefix of another. Then $C_{U} (x) \leq ∣ \overset{e}{ˉ} ∣ + C_{M_{e}} (x) = C_{M_{e}} (x) + c_{M_{e}}$ with $c_{M_{e}} = ∣ \overset{e}{ˉ} ∣$ . For two universal machines $U, U^{'}$ apply the bound in each direction: $C_{U} (x) \leq C_{U^{'}} (x) + c$ and $C_{U^{'}} (x) \leq C_{U} (x) + c^{'}$ , so $∣ C_{U} (x) - C_{U^{'}} (x) ∣ \leq max (c, c^{'})$ . $□$

Proposition 2 (Kraft-Chaitin / machine-existence theorem). Given a c.e. set of requests $(ℓ_{i}, x_{i})_{i \in ω}$ with $\sum_{i} 2^{- ℓ_{i}} \leq 1$ , there is a prefix-free machine $M$ with, for each $i$ , a program $p_{i}$ of length $ℓ_{i}$ and $M (p_{i}) = x_{i}$ .

Proof. Process requests in enumeration order, maintaining the available part of $[0, 1)$ as a finite union of dyadic intervals (the still-unassigned binary subtree). For request $(ℓ_{i}, x_{i})$ choose a dyadic interval of length $2^{- ℓ_{i}}$ from the available set, aligned at a multiple of $2^{- ℓ_{i}}$ ; assign its defining length- $ℓ_{i}$ string as $p_{i}$ with $M (p_{i}) = x_{i}$ , and remove that interval. The greedy rule — always take the leftmost available aligned interval of the required size, splitting a larger free interval if necessary — keeps the free region a union of dyadic intervals of distinct sizes, and an interval of size $2^{- ℓ_{i}}$ is always available because the total length requested so far is $\sum_{j \leq i} 2^{- ℓ_{j}} \leq 1$ , so the used length never exceeds $1$ and the alignment invariant guarantees a fitting slot. The assigned strings are pairwise prefix-incomparable (their intervals are disjoint), so $M$ is prefix-free. $M$ is computable since the request set is c.e. and the bookkeeping is finite at each stage. $□$

Proposition 3 (universal ML-test). There is a single ML-test $(U_{n})$ such that $X$ is ML-random iff $X \in / ⋂_{n} U_{n}$ ; equivalently a largest effective null set exists.

Proof. Enumerate all ML-tests effectively: a candidate is a uniformly c.e. double sequence $(U_{n}^{e})$ , and from any c.e. sequence force the measure bound by truncating $U_{n}^{e}$ at the stage its enumerated measure would exceed $2^{- n}$ (a computable guard), yielding a genuine test $(U_{n}^{e})$ that equals $(U_{n}^{e})$ when the latter is already a test. Set $U_{n} = ⋃_{e} U_{n + e + 1}^{e}$ . Then $μ (U_{n}) \leq \sum_{e} 2^{- (n + e + 1)} = 2^{- n}$ , and $(U_{n})$ is uniformly c.e., so it is an ML-test. If $X$ fails some test $(U_{n}^{e})$ , then $X \in U_{m}^{e}$ for all $m$ , in particular $X \in U_{n + e + 1}^{e} \subseteq U_{n}$ for all $n$ , so $X$ fails $(U_{n})$ . Conversely failing $(U_{n})$ is failing an ML-test. So $⋂_{n} U_{n}$ is the union of all effective null sets, the largest effective null set, and its complement is the ML-random reals. $□$

Proposition 4 ( $Ω$ is left-c.e., incomputable, and $\equiv_{T} \emptyset^{'}$ ). Chaitin's $Ω$ is the increasing limit of computable rationals, is not computable, and satisfies $Ω \equiv_{T} \emptyset^{'}$ .

Proof. Left-c.e.: $Ω_{s} = \sum_{U_{s} (p) ↓} 2^{- ∣ p ∣}$ is a computable nondecreasing sequence of rationals with limit $Ω$ (the Kraft inequality gives $Ω \leq 1$ , and $Ω > 0$ since $U$ halts on something). Incomputable: by Proposition 4's left-c.e.-ness and Schnorr-Levin (Theorem 1) $Ω$ is ML-random, and no ML-random real is computable — a computable $X$ fails the test $U_{n} = [X ↾ n]$ of measure $2^{- n}$ . For $Ω \geq_{T} \emptyset^{'}$ : given $Ω ↾ n$ , enumerate $U$ until $Ω_{s} > Ω ↾ n$ (as binary fractions); thereafter no program of length $\leq n$ can newly halt, since one would contribute $\geq 2^{- n}$ and overshoot the known prefix, so the halting set restricted to length $\leq n$ is decided — letting $n \to \infty$ , $\emptyset^{'} \leq_{T} Ω$ . For $Ω \leq_{T} \emptyset^{'}$ : $Ω$ is left-c.e., so its left cut ${q \in Q : q < Ω}$ is c.e., hence $Ω \leq_{T} \emptyset^{'}$ (the $n$ -th bit is decided by a $\emptyset^{'}$ query asking whether the approximation stabilises). So $Ω \equiv_{T} \emptyset^{'}$ . $□$

Proposition 5 (a left-c.e. ML-random real is Turing-complete). Every $Ω$ -number — every left-c.e. ML-random real — is Turing-equivalent to $\emptyset^{'}$ .

Proof. Let $α$ be left-c.e. and ML-random, with computable increasing rational approximation $α_{s} ↗ α$ . Always $α \leq_{T} \emptyset^{'}$ since the left cut is c.e. For completeness, suppose toward contradiction $α \neq \geq_{T} \emptyset^{'}$ . The key lemma (Kučera-Slaman) is that a left-c.e. real $α$ that does not compute $\emptyset^{'}$ has slow convergence in a way an ML-test can exploit: the "amount of approximation still to come past stage $s$ ", $α - α_{s}$ , is then $Π_{1}^{0}$ -approximable finely enough that the intervals $(α_{s}, α_{s} + 2^{- n})$ capturing $α$ form a uniformly c.e. sequence of measure $\leq 2^{- n}$ trapping $α$ 's binary expansion — an ML-test $α$ fails, contradicting ML-randomness. Hence $α \geq_{T} \emptyset^{'}$ , so $α \equiv_{T} \emptyset^{'}$ . (The full argument uses the Solovay reducibility of c.e. reals: $α$ ML-random and left-c.e. is Solovay-complete, and Solovay completeness implies Turing completeness.) $□$

Proposition 6 ( $K$ -lows are closed downward and $Δ_{2}^{0}$ ). Every $K$ -low set is $Δ_{2}^{0}$ , the $K$ -lows are closed under $\oplus$ , and they are downward closed under $\leq_{T}$ within the $K$ -lows via lowness for $K$ .

Proof (skeleton). A $K$ -low $A$ satisfies $K (A ↾ n) \leq K (n) + b$ for a constant $b$ . By the Nies-Hirschfeldt-Downey characterisation (Theorem 2) $A$ is low for $K$ , so $K^{A} = K + O (1)$ ; the witnessing constant is computed from $b$ . The number of sets $A$ with a fixed $K$ -lowness constant $b$ is finite at each length up to a $Π_{1}^{0}$ -bounded counting (the decanter/golden-run argument bounds how many $n$ -length strings can be $K$ -low with constant $b$ ), which places $A \leq_{T} \emptyset^{'}$ , hence $A \in Δ_{2}^{0}$ . Closure under $\oplus$ : if $A, B$ are $K$ -low with constants $b_{A}, b_{B}$ then $K ((A \oplus B) ↾ 2 n) \leq K (A ↾ n) + K (B ↾ n) + O (1) \leq K (n) + O (1) = K (2 n) + O (1)$ by subadditivity of $K$ and $K (n) = K (2 n) + O (1)$ , so $A \oplus B$ is $K$ -low. Downward closure within the class is immediate from low-for- $K$ being closed under $\leq_{T}$ . So the $K$ -lows form a $Σ_{3}^{0}$ ideal in the Turing degrees, below $\emptyset^{'}$ . $□$

Proposition 7 (Schnorr randomness is strictly weaker than ML-randomness). There is a Schnorr-random real that is not ML-random.

Proof (skeleton). A Schnorr test is an ML-test $(U_{n})$ with $μ (U_{n})$ computable as a function of $n$ (not merely $\leq 2^{- n}$ ); $X$ is Schnorr-random if it passes every Schnorr test. Every ML-random real is Schnorr-random (fewer tests to pass). For the strict separation, the universal ML-test $(U_{n})$ has measure only upper semicomputable, not computable, so it is not a Schnorr test; one constructs a real $X$ failing $(U_{n})$ — hence not ML-random — while diagonalising against every Schnorr test, using that the computable-measure constraint lets one predict the test's measure and steer $X$ out of each $⋂_{n} V_{n}$ for Schnorr $(V_{n})$ . The construction is a finite-extension argument relative to the (computable) measure approximations, in the spirit of the Kleene-Post construction of 42.04.04. Hence $X$ is Schnorr-random but not ML-random, separating the two notions. $□$

Connections Master

Turing reducibility, oracles, and the jump 42.04.04, the prerequisite, supplies the relativised machinery on which the whole degree theory of randomness rests: the oracle functionals that define relativised complexity $K^{A}$ and relativised randomness, the jump that makes $Ω \equiv_{T} \emptyset^{'}$ and indexes the $n$ -randomness ladder, and the join $\oplus$ that van Lambalgen's theorem analyses. That unit owns the jump as a measure of computational difficulty; this unit shows the same jump is a source of randomness, with $Ω$ the halting probability of $\emptyset^{'}$ made into a single ML-random real.
The Turing degrees and the priority method 42.04.06 is the structural mirror of this unit's degree theory of randomness. Where the priority method populates the interval $(0, 0^{'})$ with intermediate c.e. degrees by finite injury, the $K$ -low reals populate it with the least random sets, forming a $Σ_{3}^{0}$ c.e.-presentable ideal of low, non-cuppable degrees built by the cost-function method — a construction technique kindred to priority. The Nies-Hirschfeldt-Downey coincidence theorem is the randomness-theoretic analogue of the Friedberg-Muchnik landmark, and both live among the c.e. degrees that unit charts.
The arithmetical hierarchy and Post's theorem 42.04.05 calibrates the randomness hierarchy: $n$ -randomness is ML-randomness relative to $\emptyset^{(n - 1)}$ , weak-2-randomness uses $Π_{2}^{0}$ null sets, and ML-tests are $Σ_{1}^{0}$ classes, so the syntactic ladder of that unit is the meter for the strength of a randomness notion. The non-computability of $K$ and $C$ is upper-semicomputability — a $Σ_{1}^{0}$ approximation from above — placing the complexity functions precisely in the hierarchy that unit builds.
The halting problem and recursion theorem 42.04.02 is the source of $Ω$ and of the Berry-paradox non-computability of $C$ : the halting probability is the measure of the halting set in program space, the first $n$ bits of $Ω$ decide halting for length- $\leq n$ programs, and the proof that $C$ is non-computable is a recursion-theoretic diagonalisation against a hypothetical short description of "the least incompressible string." That unit owns the single halting diagonal; this unit weighs the halting set and finds it maximally information-dense.

Historical & philosophical context Master

The subject has three independent origins around 1964-1966. Ray Solomonoff introduced program-size complexity in 1964 as a foundation for inductive inference and a formalisation of Occam's razor, defining a universal prior over hypotheses. Andrei Kolmogorov, in his 1965 paper "Three approaches to the quantitative definition of information," proposed the complexity $C (x)$ as the algorithmic counterpart of Shannon entropy and as a definition of the information content of an individual object, independent of any probability distribution ^{[Li-Vitanyi Ch. 1]}. Gregory Chaitin, then a teenager, arrived at program-size complexity independently and pursued its connection to incompleteness and the halting probability. The plain complexity $C$ had a known defect — its failure of subadditivity and the complexity oscillations that block a clean characterisation of randomness — which Leonid Levin and Chaitin resolved in the early 1970s by passing to prefix-free machines and the complexity $K$ .

The definition of randomness for infinite sequences was given by Per Martin-Löf in 1966, a student of Kolmogorov, who replaced the failed attempt to define randomness by statistical tests alone with the notion of an effective null set and a universal test ^{[Downey-Hirschfeldt Ch. 6]}. The equivalence of randomness with incompressibility — the Schnorr-Levin theorem — was established by Claus-Peter Schnorr and Levin in the early 1970s. Chaitin's $Ω$ appeared in his 1975 paper on a theory of program size, and the modern degree theory of randomness — van Lambalgen's 1987 theorem, and the $K$ -lowness results identifying low-for-random with low-for- $K$ — was developed by Michiel van Lambalgen, André Nies, Denis Hirschfeldt, Rod Downey, Frank Stephan, and Joseph Miller in the decade after 2000, with the Kučera-Slaman characterisation of the $Ω$ -numbers and the Nies-Hirschfeldt-Downey coincidence theorem as its central results.

Bibliography Master

@article{kolmogorov1965three,
  author  = {Kolmogorov, Andrei N.},
  title   = {Three approaches to the quantitative definition of information},
  journal = {Problems of Information Transmission},
  volume  = {1},
  number  = {1},
  year    = {1965},
  pages   = {1--7}
}

@article{solomonoff1964formal,
  author  = {Solomonoff, Ray J.},
  title   = {A formal theory of inductive inference, Part I},
  journal = {Information and Control},
  volume  = {7},
  number  = {1},
  year    = {1964},
  pages   = {1--22}
}

@article{martinlof1966definition,
  author  = {Martin-L{\"o}f, Per},
  title   = {The definition of random sequences},
  journal = {Information and Control},
  volume  = {9},
  number  = {6},
  year    = {1966},
  pages   = {602--619}
}

@article{levin1974laws,
  author  = {Levin, Leonid A.},
  title   = {Laws of information conservation (non-growth) and aspects of the foundation of probability theory},
  journal = {Problems of Information Transmission},
  volume  = {10},
  number  = {3},
  year    = {1974},
  pages   = {206--210}
}

@article{schnorr1973process,
  author  = {Schnorr, Claus-Peter},
  title   = {Process complexity and effective random tests},
  journal = {Journal of Computer and System Sciences},
  volume  = {7},
  number  = {4},
  year    = {1973},
  pages   = {376--388}
}

@article{chaitin1975theory,
  author  = {Chaitin, Gregory J.},
  title   = {A theory of program size formally identical to information theory},
  journal = {Journal of the ACM},
  volume  = {22},
  number  = {3},
  year    = {1975},
  pages   = {329--340}
}

@phdthesis{vanlambalgen1987random,
  author  = {van Lambalgen, Michiel},
  title   = {Random Sequences},
  school  = {University of Amsterdam},
  year    = {1987}
}

@article{kucera1985measure,
  author  = {Ku{\v{c}}era, Anton{\'\i}n},
  title   = {Measure, $\Pi^0_1$-classes and complete extensions of {PA}},
  journal = {Lecture Notes in Mathematics},
  volume  = {1141},
  year    = {1985},
  pages   = {245--259}
}

@article{kuceraslaman2001randomness,
  author  = {Ku{\v{c}}era, Anton{\'\i}n and Slaman, Theodore A.},
  title   = {Randomness and recursive enumerability},
  journal = {SIAM Journal on Computing},
  volume  = {31},
  number  = {1},
  year    = {2001},
  pages   = {199--211}
}

@article{nies2005lowness,
  author  = {Nies, Andr{\'e}},
  title   = {Lowness properties and randomness},
  journal = {Advances in Mathematics},
  volume  = {197},
  number  = {1},
  year    = {2005},
  pages   = {274--305}
}

@book{downeyhirschfeldt2010,
  author    = {Downey, Rodney G. and Hirschfeldt, Denis R.},
  title     = {Algorithmic Randomness and Complexity},
  series    = {Theory and Applications of Computability},
  publisher = {Springer},
  year      = {2010}
}

@book{nies2009computability,
  author    = {Nies, Andr{\'e}},
  title     = {Computability and Randomness},
  series    = {Oxford Logic Guides},
  number    = {51},
  publisher = {Oxford University Press},
  year      = {2009}
}

@book{livitanyi2019introduction,
  author    = {Li, Ming and Vit{\'a}nyi, Paul},
  title     = {An Introduction to Kolmogorov Complexity and Its Applications},
  edition   = {4},
  series    = {Texts in Computer Science},
  publisher = {Springer},
  year      = {2019}
}

Prerequisites

42.04.04

Tier anchors

beginner: Li and Vitányi 2019 *An Introduction to Kolmogorov Complexity and Its Applications* 4e (Springer) Ch. 1-2 (read the informal account of the shortest program that prints a string as a measure of its information content, why most strings have no short description, and why a truly random sequence is one with no compressible pattern); Downey and Hirschfeldt 2010 *Algorithmic Randomness and Complexity* (Springer) Ch. 1 for the plain-language framing of randomness as the absence of any effective regularity
intermediate: Downey and Hirschfeldt 2010 *Algorithmic Randomness and Complexity* (Springer) Ch. 2-3, 6 (plain complexity $C$, the invariance theorem up to an additive constant, incompressibility and counting; prefix-free complexity $K$ via prefix machines and the Kraft-Chaitin theorem, subadditivity; Martin-Löf randomness via effective null sets / ML-tests and the universal test; the Schnorr-Levin theorem $X$ is ML-random iff $K(X{\restriction}n) \ge n - O(1)$); Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 14 for $C$, $K$, ML-randomness, and Chaitin's $\Omega$ in the degree-theoretic setting
master: Downey and Hirschfeldt 2010 *Algorithmic Randomness and Complexity* (Springer) Ch. 6-11 (the Schnorr-Levin characterisation, Chaitin's $\Omega$ as a left-c.e. ML-random real, van Lambalgen's theorem, the randomness hierarchy — computable, Schnorr, ML, weak-2, and 2-randomness — and the degree theory of randomness: $K$-lowness, lowness for ML-randomness, the Nies-Hirschfeldt-Downey theorem that low-for-random $=$ low-for-$K$ $=$ $K$-low, and the relation to the c.e. and Turing degrees); Nies 2009 *Computability and Randomness* (Oxford Logic Guides 51) Ch. 3, 5, 8 (the prefix-free machine theory, ML-randomness and its degree theory, the $K$-low reals and the cost-function method); Li and Vitányi 2019 *An Introduction to Kolmogorov Complexity and Its Applications* 4e (Springer) Ch. 2-4, 6 for the incompressibility method in combinatorics and average-case analysis

References

Downey, R. G. and Hirschfeldt, D. R. — Algorithmic Randomness and Complexity · Springer, Theory and Applications of Computability (2010). The canonical monograph. Ch. 2-3: PLAIN (Kolmogorov) COMPLEXITY $C(x) = \min\{|p| : U(p) = x\}$ for a fixed universal machine $U$; the INVARIANCE THEOREM that any two universal machines give $C$ functions differing by an additive constant, so $C$ is well-defined up to $O(1)$; INCOMPRESSIBILITY — for each $n$ there is a string of length $n$ with $C(x) \ge n$, and most length-$n$ strings satisfy $C(x) \ge n - c$, by counting the $2^n - 1$ programs of length $< n$ against the $2^n$ strings; the NON-COMPUTABILITY of $C$ (if $C$ were computable, 'the least string of complexity $> n$' would be computable with a short description — Berry's paradox / the connection to the halting problem); the non-subadditivity / non-monotonicity defects of $C$. PREFIX-FREE COMPLEXITY $K(x)$ defined by PREFIX MACHINES (domain an antichain under the prefix order); the KRAFT INEQUALITY $\sum_x 2^{-|p_x|} \le 1$ and the KRAFT-CHAITIN theorem building a prefix machine from any c.e. set of (length, string) requests with $\sum 2^{-\ell_i} \le 1$; $K$ is SUBADDITIVE, $K(x,y) \le K(x) + K(y) + O(1)$, repairing the defect of $C$. MARTIN-LÖF RANDOMNESS: an ML-TEST is a uniformly c.e. sequence $(U_n)$ of $\Sigma^0_1$ classes with $\mu(U_n) \le 2^{-n}$; $X$ FAILS the test if $X \in \bigcap_n U_n$ (an EFFECTIVE NULL set / effective $G_\delta$ null set); $X$ is ML-RANDOM if it passes every ML-test; the UNIVERSAL ML-test exists (a single test capturing all effective null sets), so ML-randomness is passing one test. The SCHNORR-LEVIN THEOREM: $X$ is ML-random iff $K(X{\restriction}n) \ge n - O(1)$ for all $n$ (incompressibility of every initial segment equals randomness); the analogous Levin-Schnorr with $C$ fails (complexity oscillations). CHAITIN'S $\Omega = \sum_{U(p)\downarrow} 2^{-|p|}$, the HALTING PROBABILITY of the universal prefix machine: $\Omega$ is LEFT-C.E. (a c.e. real, the increasing limit of computable rationals), ML-RANDOM, and INCOMPUTABLE; $\Omega \equiv_T \emptyset'$ and the first $n$ bits of $\Omega$ decide the halting of all programs of length $\le n$, so $\Omega$ ENCODES the halting problem. VAN LAMBALGEN'S THEOREM: $X \oplus Y$ is ML-random iff $X$ is ML-random and $Y$ is ML-random relative to $X$ (relativised randomness is symmetric). The RANDOMNESS HIERARCHY: computable-randomness, SCHNORR randomness (Schnorr tests with $\mu(U_n)$ computably converging to $0$), ML-randomness, WEAK-2-randomness, and $n$-RANDOMNESS (ML-randomness relative to $\emptyset^{(n-1)}$), strictly increasing. $K$-LOWNESS: $X$ is $K$-LOW if $K(X{\restriction}n) \le K(n) + O(1)$ (initial segments as compressible as possible — the antithesis of random); LOWNESS FOR ML-RANDOMNESS ($X$ adds no power as an oracle to derandomise) and LOWNESS FOR $K$; the NIES-HIRSCHFELDT-DOWNEY THEOREM that $K$-LOW $=$ LOW FOR $K$ $=$ LOW FOR ML-RANDOM, all $\Delta^0_2$ and closed downward, forming a $\Sigma^0_3$ c.e.-presentable ideal in the Turing degrees strictly inside the low and the non-cuppable degrees; the COST-FUNCTION method building $K$-lows. The c.e. and Turing degree interface, cross-ref the priority method.
Nies, A. — Computability and Randomness · Oxford University Press, Oxford Logic Guides 51 (2009). Ch. 2: PREFIX-FREE machines, the Kraft-Chaitin (machine-existence) theorem, $K$ and $C$ and the basic relations $K(x) \le C(x) + 2\log C(x) + O(1)$ and $C(x) \le K(x) + O(1)$, the COUNTING/incompressibility theorems, the AMOUNT of information and symmetry of information $K(x,y) = K(x) + K(y \mid x^*) + O(1)$ (Levin-Gács). Ch. 3: MARTIN-LÖF RANDOMNESS via tests and via the universal c.e. supermartingale (Solovay tests, the SCHNORR-LEVIN characterisation through $K$, the ample-excess lemma $\sum_n 2^{n - K(X{\restriction}n)} < \infty$ for ML-random $X$); $\Omega$ as a left-c.e. ML-random real and the SOLOVAY-degree theory of c.e. reals (the $\Omega$-numbers are exactly the c.e. ML-random reals, Calude-Hertling-Khoussainov-Wang / Kučera-Slaman). Ch. 5-6: the test hierarchy — computable, Schnorr, ML, weak-2, 2-randomness — and van Lambalgen's theorem; randomness and the TURING/c.e. degrees, the Kučera-Gács theorem that every set is computed by an ML-random set, BASES FOR ML-RANDOMNESS. Ch. 5, 8: $K$-LOWNESS and LOWNESS — the equivalence $K$-low $=$ low for $K$ $=$ low for ML-random $=$ a base for ML-randomness (Nies, Hirschfeldt, Downey, with the decanter and golden-run combinatorics), the COST-FUNCTION construction, the closure of the $K$-lows under $\oplus$ as a $\Sigma^0_3$ ideal, and their location strictly below $\emptyset'$, inside the low and the non-cuppable c.e. degrees.
Li, M. and Vitányi, P. — An Introduction to Kolmogorov Complexity and Its Applications · Springer, Texts in Computer Science, 4th ed. (2019). Ch. 1-2: the three founding motivations (Solomonoff's inductive inference, Kolmogorov's information measure, Chaitin's program-size complexity), PLAIN COMPLEXITY $C$, the invariance theorem, conditional complexity $C(x \mid y)$, incompressibility and the counting argument, the non-computability of $C$ and the upper-semicomputability that survives. Ch. 3: PREFIX COMPLEXITY $K$, the Kraft inequality, the relation to a universal lower-semicomputable semimeasure $\mathbf m$ and the CODING THEOREM $K(x) = -\log \mathbf m(x) + O(1)$ (Levin), the symmetry of information. Ch. 4: ALGORITHMIC randomness of finite strings and infinite sequences, Martin-Löf's definition, the relation between incompressibility and statistical typicality, NORMALITY (Borel-normal sequences are a measure-1 class implied by randomness but strictly weaker). Ch. 6: the INCOMPRESSIBILITY METHOD — a proof technique in which one fixes an incompressible object and derives combinatorial bounds (lower bounds for sorting and Turing-machine running time, the average-case analysis of algorithms, Ramsey-type and graph results, prime-gap and number-theoretic estimates), the algorithmic-information-theoretic replacement for the probabilistic method. Ch. 8 for the relation to Shannon entropy and the thermodynamic / Maxwell-demon connections.

Estimated time

beginner: 20m
intermediate: 55m
master: 105m