How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Kolmogorov Complexity and Algorithmic Randomness: Examples and Counterexamples

1 · Prerequisites

2 · Summary

The examples make counting, dimension, and machine-dependence concrete.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-adaptedjudge pass (gpt-5.6-terra)audited 2026-09-07Open item page →

Counting incompressible strings of a fixed length

Example

For every fixed description machine $M$ , fewer than $2^{90}$ of the $2^{100}$ strings of length $100$ have $C_{M}$ -complexity below $90$ ; equivalently, the proportion is strictly less than $1 / 1024$ .

Facts & Assumptions

Given: $n = 100, c = 10$ .

Verification

1.1

The compression threshold is $n - c = 90$ .

given

2.1

For the fixed machine $M$ , Most finite strings are incompressible bounds the number by strictly less than $2^{100 - 10} = 2^{90}$ , hence the proportion by strictly less than $2^{- 10} = 1 / 1024$ .

step 1.1algebra∎

ExampleConstruction: Literature-sourcedVerification: AI-adaptedjudge pass (gpt-5.6-terra)audited 2026-09-07Open item page →

An effective-dimension calculation from prefix complexity

Example

If $K (X ↾ n) = n / 2 + o (n)$ along every sufficiently large $n$ , then $\dim (X) = 1 / 2$ .

Verification

Given: the displayed asymptotic equality.

1.1

Dividing by $n$ gives $K (X ↾ n) / n = 1 / 2 + o (1)$ .

given

2.1

Its liminf is $1 / 2$ , and Effective dimension is the liminf prefix-complexity rate identifies this with $\dim (X)$ .

step 1.1algebra∎

CounterexampleConstruction: Literature-sourcedVerification: AI-adaptedjudge pass (gpt-5.6-terra)audited 2026-09-07Open item page →

Changing an optimal machine changes finite-string complexity

Statement refuted

Optimal machines give identical numerical complexities.

Counterexample

Given: an optimal machine $U$ and a finite word $z$ with $C_{U} (z) > 1$ .

1.1

Define $V (0 p) = U (p)$ and $V (1) = z$ . The simulation shows $V$ remains optimal.

given

2.1

Then $C_{V} (z) = 1 < C_{U} (z)$ , contradicting identical values and instantiating False: Kolmogorov complexity is an absolute integer.

step 1.1given∎

Kolmogorov Complexity and Algorithmic Randomness: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Counting incompressible strings of a fixed length

Example

Facts & Assumptions

Verification

An effective-dimension calculation from prefix complexity

Example

Verification

Changing an optimal machine changes finite-string complexity

Statement refuted

Counterexample

Sources