Source-linked AI summary
Randomness Conservation Inequalities; Information and Independence in Mathematical Theories
Leonid A. Levin
TL;DR
The paper takes as its organizing problem the formalization, justification, and application of a physical independence principle. It develops randomness and information conservation results, and reports that formalizing the Independence Postulate radically simplifies theories of random sequences, intuitionistic free-choice sequences, and regular Turing-degree representatives.
Problem
The paper’s organizing problem is to formalize, justify, and apply a physical principle concerning independence.
Source: §0.1 · p. 2Method
The paper develops randomness and information conservation, including the theorem that recursive random transformations do not increase randomness divergence.
Source: §2.2 · p. 6Results
Formalizing the Independence Postulate radically simplifies theories of random sequences, intuitionistic free-choice sequences, and representatives of regular Turing degrees.
Source: §0.1 · p. 2Takeaways & Limitations
The Law of Independence is a probability-theory law whose formulation I(α : β) < ∞ does not mention the probability measure.
Source: §3.3 · p. 9Incomplete sequences can arise from partial recursive projections, so Chapter 4 uses an axiom that intuitively treats every physical sequence as a projection of a complete one.
Source: §2.3 · p. 7
Abstract
from arXiv · showhide
The article develops further Kolmogorov's Algorithmic Complexity Theory. The definition of Randomness is modified to satisfy strong invariance properties (conservation inequalities). This allows definitions of concepts such as Mutual Information in individual infinite sequences. Applications to several areas, like Probability Theory, Theory of Algorithms, Intuitionistic Logic are considered. These theories are simplified substantially with the postulate that the objects they consider are independent of (have small mutual information with) any sequence specified by a mathematical property.
0 Initial Remarks
The introduction presents algorithmic information theory as a recursively invariant framework for complexity, randomness, and information, and organizes the work around formalizing and applying an independence principle. It also reviews limitations in earlier randomness and information definitions and sets out conventions for the theory’s recursive measures and transformations.
0.1 Introduction
- K(x) is tied to shortest-program length through a universal measure, whose absorbing element m dominates recursively enumerable summable sequences.The introduction describes m as a universal measure and gives its construction from an r.e. family of non-negative sequences with sum bounded by 1.Source: §0.1 · p. 1
- The paper organizes its work around formalizing, justifying, and applying a physical principle concerning independence between a physically generated sequence and one specified by a mathematical property.The proposed postulate bounds their mutual information by the description lengths of the process and property.Source: §0.1 · p. 2
0.2 Brief References
- The cited prior work left randomness definitions difficult to extend beyond recursive measures and information definitions with errors large enough to obscure mutual-information differences.The discussion traces later improvements to universal-measure-based definitions of randomness and information that extend to infinite sequences.Source: §0.2 · p. 2
0.3 Conventions
- The conventions model measures and random transformations as operators, and represent random partial processes with semimeasures that may lose mass.The text identifies measures with positive linear functionals and random partial transformations with positive uniform concave operators.Source: §0.3 · p. 3
- The paper’s proofs are succinct but require slow reading and frequent reference to the conventions, while remaining independent enough to follow selectively.The authors state that many proofs can be skipped without preventing understanding of the others.Source: §0.3 · p. 3
1 Discrete Case
The discrete case develops algorithmic complexity, randomness deficiency, and mutual information for individual objects, then establishes conservation of independence under processing. It also applies time-bounded complexity to characterize search costs, including randomized search.
1.1 Complexity, Randomness and Information
- A prefix algorithm can generate x using an input of volume K(x), and no prefix algorithm can improve that length by more than a constant.The coding proposition supplies the matching upper and lower bounds.Source: §1.1 · p. 3
- Randomness deficiency d(x/µ) is the largest µ-test within an additive constant, with d(x/µ) ≍ |ln µ(x)| − K(x).The paper calls it a universal characteristic of non-randomness with respect to µ.Source: §1.1 · p. 4
- Mutual information can be treated as a deficiency of independence for individual objects, not only as a relation between probability distributions.The paper relates this quantity to the small randomness deficiency of a pair under the product of universal measures.Source: §1.1 · p. 4
1.2 Conservation of Independence
- Mutual information is invariant under random or recursive processing, and the paper’s conservation results support the Independence Postulate for combinations of such processes.The elementary proposition is described as an instance of the later conservation theorem and as implying conservation under combinations of random and deterministic processes.Source: §1.2 · p. 4
1.3 Time of Computation
- Searching candidates in increasing Kt order gives a fastest algorithm within a constant factor for any search problem, while C(F) determines the time needed to hit F.For randomized search, C(fs/s) characterizes a search problem’s complexity; the text asks how the complexity of obtaining suitable outputs grows.Source: §1.3 · pp. 5–6
2 Continuous Case
The section introduces a universal r.e. semimeasure as an a priori probability and develops randomness deficiency and mutual information for sequences or semimeasures. Its conservation result bounds deficiency under r.e. transformations, while complete sequences have measure-one and closure properties with a boundary at partial projections.
2.1 Universal Semimeasure
- A universal r.e. semimeasure exists, and Proposition 3 is its special case using averages of elementary semimeasures.Source: §2.1 · p. 6
- M serves as an a priori probability because its broad class of positive-probability sets makes the properties expected under a random distribution narrowest and predictable in advance.Source: §2.1 · p. 6
2.2 Randomness and Information; Conservation Laws
- Under an r.e. transformation A, D(A(µ1)/A(µ2)) ≺ D(µ1/µ2); for operators preserving µ, D(α/µ) is invariant within a constant.Source: §2.2 · pp. 6–7
- I(α : β) = D((α, β)/M⊗M) measures information in α about β, or their deficiency of independence; applying A to α cannot increase it beyond a constant.Source: §2.2 · p. 7
2.3 Complete Sequences
- For every recursive measure µ, C has full µ-measure and is preserved by total recursive operators; any α independent of β has a completion (α, τ) that is complete and independent of β.Source: §2.3 · p. 7
- A sequence projected from a complete pair may lie outside C when the projection is partial recursive but not total.Source: §2.3 · p. 7
3 Foundations of Probability Theory
The section identifies a gap between probability-one laws and the ability to assess properties selected after observing an outcome, then presents randomness and independence laws. It concludes that every µ-null probabilistic law is covered by randomness deficiency or dependence on some sequence.
3.1 Foundational Difficulties (A historical digression)
- Probability-one properties cannot all be guaranteed jointly, leaving classical theory without a rigorous basis for rejecting post hoc statistical anomalies.Source: §3.1 · p. 8
- Kolmogorov’s response selects simply expressible properties; in the infinite case, randomness with respect to µ implies the other good properties of µ-measure 1.Source: §3.1 · p. 8
3.2 The Laws of Randomness and Independence
- A µ-test formalizes a good probability law through an effectively discoverable deviation degree, with infinite deviation occurring with probability zero.Source: §3.2 · p. 9
- For α chosen randomly with distribution µ, the Law of Randomness requires D(α/µ) << ∞.Source: §3.2 · p. 9
- For a chosen sequence β, the Law of Independence requires a random α to satisfy I(α : β) << ∞.Source: §3.2 · p. 9
3.3 Covering the Classical Formulation of Probability Theory
- The Law of Independence is violated only with probability zero and depends on β, not on a probability distribution µ.Source: §3.3 · p. 9
- For any A with µ(A) = 0, some β satisfies A ⊂ Dµ ∪ Iβ, so the Laws of Randomness and Independence cover every such probabilistic law.Source: §3.3 · p. 9
4 Intuitionistic Mathematics
The section motivates an intuitionistic theory that formalizes independence to address the difficulty of grounding principles in physical intuition. It presents AI + ¬(CT) as a maximal conservative extension of classical arithmetic, with the same absolute closed theorems.
4.1 A Digression
- Unclear notions of free choice make it difficult to select principles that adequately reflect physically generated sequences, leaving no canonical intuitionistic theory with completeness.The theories discussed may be equiconsistent with classical theories while leaving other intuitionistic principles independent.Source: §4.1 · p. 10
4.3 The Calculus AI; its Relative Consistency and Completeness
- AI formalizes the Independence Postulate, excluding sequences with unbounded information about the validity of mathematical statements.The postulate is intended to yield a conservative extension while making the theory complete.Source: §4.1 · p. 10
4.2 The Preliminary Calculus A
- The preliminary calculus A uses second-order arithmetic, and its absolute formulas have identical meaning and equivalent provability in intuitionistic and classical theories.A includes first-order arithmetic, sequence variables, and quantification over sequences.Source: §4.2 · p. 10
- For every formula F, an absolute formula P exists such that A proves F exactly when it proves ∀α∃β P.The proof uses a realizability construction relative to a universal sequence.Source: §4.2 · p. 11
4.3 The Calculus AI; its Relative Consistency and Completeness
- AI + ¬(CT) has the same absolute closed theorems as classical first-order arithmetic and admits no essential extension preserving that property.It is therefore a maximal conservative extension of classical arithmetic.Source: §4.3 · p. 12
- In AI + ¬(CT), rejecting a closed formula is equivalent to its rejection for almost all sequences under a recursive continuous measure.The proof reduces formulas to an absolute form and uses invariance under recursive reversible transformations and a zero-one law.Source: §4.3 · p. 12
- For a continuous r.e. measure and another r.e. measure, recursive deterministic reciprocal transformations relate them on almost all nonrecursive sequences.This measure-translation result is used in the argument for the calculus's relative consistency and completeness.Source: §4.3 · p. 12
5 Theory of Turing Degrees
The section uses information-based independence to define negligible sets and compare Turing-degree properties up to negligibility. For regular sequences, every Turing-invariant Borel set reduces to one of four cases, determined by recursiveness.
5.1 Independence and Negligible Sets
- Reducibility can call sequences independent even when 99 percent of their random contents coincide, motivating an informational account of independence.The example defines β by XORing independent random sequences α and γ, with γ having probability 0.99 of a zero.Source: §5.1 · p. 13
- Negligible sets are defined using independence and recursive-operator closure, and sets differing by a negligible set are i-equivalent.The resulting factor-algebra L is formed from the Boolean algebra of Borel sets of Turing degrees.Source: §5.1 · p. 13
- A set is negligible exactly when it satisfies each of three conditions: common dependence, containment in a measure-zero inaccessible set, and universal semimeasure zero.The equivalence of “some” and “any” r.e. measure in the second condition follows from Lemma 5.Source: §5.1 · p. 13
5.2 Types of Turing Degrees
- Incomplete sequences are close to negligible, while regular sequences are defined as those Turing-equivalent to complete sequences.The paper notes that incomplete sequences cannot arise through a process bounded in time by a total recursive operator.Source: §5.2 · p. 13
- Every Turing-invariant Borel set of regular sequences is i-equivalent to the empty set, the recursive sequences, all regular sequences, or all regular nonrecursive sequences.Thus, up to i-negligibility, regular-sequence properties depend only on recursiveness.Source: §5.2 · pp. 13–14
- For nonregular Turing-degree types, it is difficult even to prove that their union is not negligible.The paper also reports an infinitely divisible element and countably many atoms in L; only two of those atoms contain complete sequences.Source: §5.2 · p. 14