Alphabeta MathHow 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
- Acceptable Numberings, the s-m-n Theorem, and Recursion
- Compactness in Metric Spaces
- Construction of the Natural Numbers
- Construction of the Real Numbers via Cauchy Sequences
- Construction of the Real Numbers via Dedekind Cuts
- Countability and Uncountability
- Decidable, Recognizable, and Enumerable Languages
- Finite Counting, Factorials and Binomial Coefficients
- Finite Probability Spaces and Random Variables
- Formal Languages, Encodings, and Decision Problems
- Foundations of the Real Numbers for Analysis
- Kolmogorov Complexity and Algorithmic Randomness
- limsup, liminf, and Subsequential Limits
- Linear Recurrences and Rational Generating Functions
- Measure Preserving Transformations and Poincare Recurrence
- Measures and Their Basic Properties
- Metric Spaces
- Order, Zorn's Lemma, and the Axiom of Choice
- Outer Measure and the Caratheodory Extension Theorem
- Primitive Recursive and Partial Computable Functions
- Relations, Functions, and Quotients
- Robust Machine Models and Universal Computation
- Roots, Rational Powers, and Classical Inequalities
- Sequences and Limits
- Sigma Algebras and Borel Sets
- Suprema and Infima
- The ZFC Axioms and the Basic Set Constructions
- Turing Machines, Configurations, and Computation
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
Counting incompressible strings of a fixed length
Example
For every fixed description machine , fewer than of the strings of length have -complexity below ; equivalently, the proportion is strictly less than .
Facts & Assumptions
Given: .
Verification
The compression threshold is .
For the fixed machine , Most finite strings are incompressible bounds the number by strictly less than , hence the proportion by strictly less than .
An effective-dimension calculation from prefix complexity
Example
If along every sufficiently large , then .
Verification
Given: the displayed asymptotic equality.
Dividing by gives .
Its liminf is , and Effective dimension is the liminf prefix-complexity rate identifies this with .
Changing an optimal machine changes finite-string complexity
Statement refuted
Optimal machines give identical numerical complexities.
Counterexample
Given: an optimal machine and a finite word with .
Define and . The simulation shows remains optimal.
Then , contradicting identical values and instantiating False: Kolmogorov complexity is an absolute integer.