Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Glossary

Short descriptions of terms defined throughout these notes, each with a link to its full definition.

A priori complexity
The complexity KM⁡(σ):=−log⁡M(σ)\operatorname{KM}(\sigma) := -\log \mathbf{M}(\sigma) of a string, given by the optimal lower-semicomputable continuous semimeasure M\mathbf{M}. See Section 1.5.
A priori discrepancy
The gap ΔM⁡ρ(σ):=KM⁡(σ)+log⁡ρ([σ])\operatorname{\Delta M}_\rho(\sigma) := \operatorname{KM}(\sigma) + \log \rho([\sigma]) between a string’s a priori complexity and its mass under a premeasure ρ\rho. See Definition 1.6.1.
A priori probability
The total weight QM(a):=∑M(π)↓=a2−len⁡(π)Q_M(a) := \sum_{M(\pi) \downarrow = a} 2^{-\operatorname{len}(\pi)} of all descriptions of a finitary object aa under a machine MM. See Definition 1.5.1.
Absolutely continuous
An outer measure ν\nu is absolutely continuous with respect to μ\mu, written ν≪μ\nu \ll \mu, if every μ\mu-null set is ν\nu-null. See Section 1.1.
Algorithm
A procedure implementable by an oracle Turing machine equipped with an appropriate oracle. See Section 4.1.3.
Algorithmic probability
The value RM(a):=2−CM(a)R_M(a) := 2^{-C_M(a)} given by a finitary object’s shortest description under a machine MM. See Definition 1.5.1.
Arithmetic hierarchy
Kleene’s classification of sets of natural numbers into levels Σn0\Sigma^0_n, Πn0\Pi^0_n, Δn0\Delta^0_n by the number of alternating quantifiers needed to define them from a computable relation. See Section 1.2.
Bayes’ Rule
A rule for induction updating a hypothesis’s likelihood on additional observations via conditional probabilities. See Section 4.1.2.
Bi-uniformly continuous
A bijection that is both uniformly continuous and co-uniformly continuous; “bi-Lipschitz” and “bi-Hölder” are used likewise. See Section 2.6.
Cauchy representation
A sequence of dyadic approximations to a real point xx, the rr-th accurate to within 2−r2^{-r}; it is standard if each approximation rounds xx down. See Section 1.2.
Chain rule
An approximate formula relating the complexity of a pair to a sum of complexities involving both terms. Originally, Gács’s identity: K(a,b∣c)=K(a∣c)+K(b∣a,K(a),c)±O(1)K(a, b \mid c) = K(a \mid c) + K(b \mid a, K(a), c) \pm O(1) for prefix complexity of finitary objects. Also called symmetry of information, analogous to that of Shannon information theory. See Theorem 1.3.1.
Co-Lipschitz constant
A constant lower-bounding how much a function shrinks distances: no two points are mapped closer together than this many times their original distance. See Section 2.6.
Co-uniformly continuous
An injection whose inverse is uniformly continuous; “co-Lipschitz” and “co-Hölder” are used likewise. See Section 2.6.
Coding Theorem
Levin’s theorem that prefix complexity and the negative logarithms of algorithmic probability, a priori probability, and the optimal lower-semicomputable discrete semimeasure all agree up to an additive constant. See Theorem 1.5.2.
Comparable
Two strings are comparable (σ∣∣τ\sigma \mid\mid \tau) if one extends the other. See the Notation page.
Complexity notion
A numerical measure of a hypothesis’s inherent complexity against some fixed set of simple primitives. Usually a map assigning a score along its domain, with a smaller score meaning simpler. See Sections 4.1.1 and 4.1.3.
Compression algorithm
An algorithm on finitary objects with an algorithmic inverse on its whole domain, read as compression (forward) and decompression (backward). See Section 4.1.3.
Computable metric space
A metric space with a dense sequence whose pairwise distances is computable. See Section 1.2.
Computable Polish space
A computable metric space whose metric is complete. See Section 1.2.
Computable real function
A function f:Rm→Rnf : \mathbb{R}^m \to \mathbb{R}^n computed by an oracle machine that turns any Cauchy representation of an input into a Cauchy representation of its output under ff. See Section 1.2.
Computably compact
A subset of a computable metric space that is empty or computably approximable, to any desired precision in Hausdorff distance, by finite subsets of the dense sequence. See Section 1.2.
Computably enumerable
A set that is the domain of a Turing machine. Equivalently, a set which is either empty or the range of a total computable function. Abbreviated “c.e.” See Section 1.2.
Conditional dimension
The quantity dim⁡(x∣y)\dim(x \mid y) quantifying the asymptotic rate of conditional complexity per bit of precision of xx given yy. See Section 2.3.
Constructive dimension
J. Lutz’s effective analogue of Hausdorff dimension, cdim⁡(X)\operatorname{cdim}(X): the infimum of ss such that some constructive ss-supergale succeeds on XX. See Section 2.2.
Constructive supergale
A lower-semicomputable supergale. See Section 1.5.
Continuous semimeasure
A map on a sequence space whose value on each string is at least the combined value on its immediate extensions, so mass can only leak away as strings grow. See Section 1.5.
Conull set
A set whose complement is null. In particular, Y⊆XY \subseteq X is μ\mu-conull in XX if μ(X∖Y)=0\mu(X \setminus Y) = 0. See Section 1.1.
Convex premeasure
A premeasure on Cantor space whose value on each string is at most the combined value on its two one-bit extensions. See Section 1.1.
Counting Theorem
Chaitin’s bounds on prefix complexity over the strings of a fixed length nn: the most complex have complexity about n+K(n)n + K(n), and few strings fall far below it. See Theorem 1.3.5.
Cover
A Martin-Löf-type test (Un)n(U_n)_n covers XX if XX is a subset of the union of all cover elements; a Solovay-type test covers XX if each point of XX has infinitely many prefixes in it. Otherwise XX passes the test. See Definition 1.4.3.
Cylinder set
The set [σ][\sigma] of all infinite binary strings extending a finite string σ\sigma. See the Notation page.
Dimension function
A non-negative, non-decreasing, right-continuous function hh on [0,∞)[0, \infty) with h(t)=0h(t) = 0 exactly when t=0t = 0. Also called a gauge. See Section 1.1.
Direct weight
The total premeasure DW⁡ρ(V)\operatorname{DW}_\rho(\mathcal{V}) of the cylinders of a collection of strings. See Definition 1.4.1.
Discrete semimeasure
A map on a collection of finitary objects whose values sum to at most 1. See Section 1.5.
Effective algorithm
An algorithm needing no oracle: a Turing machine, or a program in any Turing-complete language; i.e., computable. See Section 4.1.3.
Effective compression algorithm
A compression algorithm whose forward and backward maps are both effective algorithms. See Section 4.1.3.
Effective Hausdorff dimension
The infimum of ss for which XX is Martin-Löf-ss-null; it coincides with constructive dimension and the lower incompressibility ratio. See Section 2.2.
Effectively closed
The complement of an effectively open set; a Π10\Pi^0_1-class. See Section 1.2.
Effectively compact
A computable metric space that is computably compact in itself. See Section 1.2.
Effectively open
A set [S][S] of Cantor space generated by a c.e. set of strings SS; a Σ10\Sigma^0_1-class. See Section 1.2.
Entropy notion
A complexity notion satisfying some universality property across a class of other complexity notions. See Section 4.1.3.
Epicurus’ Principle of Multiple Explanations
A principle of induction: every hypothesis consistent with all observations ought to keep some nonzero likelihood. See Section 4.1.2.
Exact gauge
A dimension function hh with 0<Hh(X)<∞0 < \mathcal{H}^h(X) < \infty for a given set XX. See Section 1.1.
Expansive map
A map ff on Cantor space is α\alpha-expansive if, for all but finitely many rr, the first rr bits of an input determine at least α⋅r\alpha \cdot r bits of its output. See Section 2.6.
Extension
A string τ\tau extends σ\sigma (σ⪯τ\sigma \preceq \tau) if it agrees with σ\sigma on every position of σ\sigma; a proper extension is one with σ≠τ\sigma \neq \tau. See the Notation page.
Finitary object
An element of a standard countable collection such as ω\omega, 2<ω2^{<\omega}, D\mathbb{D}, or Q\mathbb{Q}, all identified by computable bijections; also called hereditarily finite. See the Notation page.
Fit oracle
An oracle that satisfies the second (fitness) condition in the definition of an optimal Hausdorff or packing oracle, but not necessarily the first. See Definition 3.1.10.
Gauge
Another name for a dimension function. See Section 1.1.
Hausdorff dimension
The infimum of s≥0s \geq 0 for which a set is null with repect to the ss-dimensional outer Hausdorff measure. See Section 1.1.
Hausdorff distance
The infimum of ε>0\varepsilon > 0 for which two sets are ε\varepsilon-close: every point of each lies within ε\varepsilon of the other. See Section 1.2.
Hausdorff gauge-regular
A set with an exact gauge hh such that lim inf⁡t→0+log⁡h(t)/log⁡t\liminf_{t \to 0^+} \log h(t) / \log t matches the Hausdorff dimension of the set. In particular, every ss-set is Hausdorff gauge-regular. See Section 1.1.
Hausdorff measure-regular
A set XX for which some metric outer measure μ\mu with 0<μ(X)<∞0 < \mu(X) < \infty has dim⁡‾H⁡(μ⌞X)=dim⁡H⁡(X)\overline{\dim}_{\operatorname{H}}(\mu \llcorner X) = \dim_{\operatorname{H}}(X); that is, deleting a μ\mu-null set from XX never lowers its Hausdorff dimension. See Section 1.1.
Hausdorff oracle
An oracle that attains the minimum in the Point-to-Set Principle for a set’s Hausdorff dimension. See Section 2.4.
Hausdorff outer measure
A Method II outer measure induced by a Hausdorff premeasure. See Section 1.1.
Hausdorff premeasure
The premeasure ρh\rho_h that applies a dimension function hh to the diameter of a set. See Section 1.1.
Hypothesis
A model for describing the source of some observations. See Section 4.1.1.
Hölder continuous
Uniformly continuous with a modulus that needs about 1/α1/\alpha bits of input precision per bit of output precision, where α\alpha is its exponent; equivalently, output distances are bounded by a constant times the α\alpha-th power of input distances. See Section 2.6.
Induction
Reasoning that reassigns likelihoods to hypotheses upon receiving more observations; also called inductive reasoning. See Section 4.1.2.
Infinitary object
An object arising from finitary objects by a limiting process, such as an infinite binary string or a real number. See the Notation page.
Information content measure
Levin’s notion: an upper-semicomputable partial function F:⊆N→ωF : \subseteq \mathscr{N} \to \omega on a collection of finitary objects with ∑a2−F(a)≤1\sum_a 2^{-F(a)} \leq 1. See Section 1.5.
Inverse-modulus
A modulus of uniform continuity for the inverse of a co-uniformly continuous map. See Section 2.6.
K-minimizer
A finitary element x∈Xx \in X witnessing the minimum complexity K(x)=K(X)K(x) = K(X); an ε\varepsilon-approximate KK-minimizer has K(x)≤K(X)+εK(x) \leq K(X) + \varepsilon. See Definition 2.1.1.
Kraft Inequality
The bound that 2−K2^{-K}, summed over any collection of finitary objects, is at most 1; a consequence of the universal machine being prefix-free. See Theorem 1.3.4.
Left-approximator
A computable map f^(i,r)\widehat{f}(i, r) that increases in rr to f(i)f(i), witnessing that ff is lower-semicomputable. See Section 1.2.
Length-invariant
A premeasure on Cantor space whose value on σ\sigma depends only on len⁡(σ)\operatorname{len}(\sigma). See Section 1.1.
Lightface Borel hierarchy
The effective hierarchy of Σn0\Sigma^0_n-, Πn0\Pi^0_n-, and Δn0\Delta^0_n-classes of Cantor space, built up from effectively open sets. See Section 1.2.
Likelihood
A numerical measure of a hypothesis’s credibility. See Section 4.1.1.
Linear sensitivity
Bounds on how much Kr(x)K_r(x) and Kr∣s(x∣y)K_{r \mid s}(x \mid y) can change when a precision-level grows: at most linearly in the change. See Lemmas 2.1.2 and 2.1.3.
Lipschitz constant
A constant upper-bounding how much a function stretches distances: no two points are mapped farther apart than this many times their original distance. See Section 2.6.
Lipschitz continuous
Uniformly continuous with a modulus that costs only a constant number of extra bits of input precision; equivalently, having a Lipschitz constant. See Section 2.6.
Local dimension
The (lower) local dimension of a set: the worst case, over its points, of the lower asymptotic rate at which a semimeasure or outer measure decays along their prefixes. See Definition 2.2.1.
Locally Lipschitz continuous
Lipschitz continuous on some open neighborhood of each point of the domain. See Section 2.6.
Locally optimal
N. Lutz’s optimality property for an outer measure among all strongly finite, lower-semicomputable outer measures. See Section 2.2.
Lower incompressibility ratio
The worst case across all points in a set of the lower asymptotic prefix complexity per bit of their prefixes. See Section 2.2.
Lower-semicomputable
A real number, or a real-valued map on a collection of finitary objects (such as a semimeasure), whose lower graph {(n,q):q<f(n)}\set{(n, q)}{q < f(n)} is c.e.; equivalently, one approximable from below by a computable left-approximator. Also called left-c.e. See Section 1.2.
Marstrand-Mattila Projection Theorem
A theorem in geometric measure theory stating that, for a broad range of subsets of Euclidean space, the Hausdorff dimension of their orthogonal projections is almost always as large as possible. Originally proved for analytic sets, and later for weakly regular sets and sets with optimal Hausdorff oracles. See Theorem A.1.
Martin-Löf test
A uniformly-c.e. sequence (Un)n(U_n)_n of sets of strings, each of which having direct weight at most 2−n2^{-n}; strong and vehement versions bound the prefix or vehement weight instead. See Definition 1.4.2.
Method II outer measure
Rogers’s outer measure Hρ\mathcal{H}^\rho induced by a premeasure ρ\rho, using covers of diameter at most δ\delta (the δ\delta-contents Hδρ\mathcal{H}^\rho_\delta) and letting δ→0\delta \to 0. See Section 1.1.
Minimal description
A description π\pi of a finitary object aa (given bb) of the least possible length; any π\pi with Mb‾(π)=aM^{\overline{b}}(\pi) = a is an MM-description. See Section 1.3.
Minimum Description Length Principle
A principle of selection preferring the hypothesis with both the simplest description and the simplest explanation of the observations. Abbreviated MDL. See Section 4.1.2.
Modulus and data processing inequalities
Bounds on how conditional prefix complexity changes under computable, uniformly continuous maps, controlled by their moduli. See Lemma 2.6.2.
Modulus of uniform continuity
A non-decreasing μ:ω→ω\mu : \omega \to \omega telling how much input precision suffices for a desired output precision: inputs within 2−μ(r)2^{-\mu(r)} of each other have outputs within 2−r2^{-r}. See Definition 2.6.1.
Mutual dimension
Case and Lutz’s lower and upper mutual dimensions mdim⁡(x:y)\operatorname{mdim}(x : y) and Mdim⁡(x:y)\operatorname{Mdim}(x : y): the asymptotic rates of mutual information per bit of precision shared by xx and yy. See Section 2.3.
Mutual information
The algorithmic information I(a:b∣c):=K(a∣c)−K(a∣b,c)I(a : b \mid c) := K(a \mid c) - K(a \mid b, c) shared by finitary objects, lifted to sets and to reals at given precision-levels. See Section 2.3.
Neighborhood
The δ\delta-neighborhood of a subset of a metric space consists of all points within distance δ\delta of that subset. See the Notation page.
Null set
A set of outer measure zero. In particular, μ\mu-null means μ(X)=0\mu(X) = 0, and ss-null means Hs(X)=0\mathcal{H}^s(X) = 0. See Section 1.1.
Observations
Data observed from some source. See Section 4.1.1.
Occam’s Razor Principle
A principle of selection preferring the simplest hypothesis consistent with all observations; more generally, that simpler hypotheses ought to get greater likelihoods. See Section 4.1.2.
Optimal
A notion of universality in which an element of a class (of semimeasures, supergales, outer measures, ...) dominates each other element of the class up to a multiplicative constant. E.g., m\mathbf{m} and M\mathbf{M} are optimal among the lower-semicomputable discrete and continuous semimeasures, respectively. See Section 1.5.
Optimal cover
A cover of a set of strings whose direct weight equals the vehement weight of the set. See Definition 1.4.7.
Optimal Hausdorff oracle
A Hausdorff oracle AA for XX such that, for every oracle BB and ε>0\varepsilon > 0, some x∈Xx \in X has dim⁡A,B(x)≥dim⁡H⁡(X)−ε\dim^{A,B}(x) \geq \dim_{\operatorname{H}}(X) - \varepsilon and KrA,B(x)≥KrA(x)−εrK^{A,B}_r(x) \geq K^A_r(x) - \varepsilon r for all but finitely many rr. See Definition 3.1.1.
Optimal packing oracle
The packing analogue of an optimal Hausdorff oracle, using packing oracles, Dim⁡\operatorname{Dim}, and dim⁡P⁡\dim_{\operatorname{P}}. See Definition 3.1.1.
Oracle
Extra information, given as a finite or infinite binary string (an infinite tape of data), that an oracle machine may consult during a computation. See Section 1.2.
Oracle machine
A Turing machine that may also query, finitely often, the bits of an oracle during its computation; also called an oracle Turing machine or Turing functional. See Section 1.2.
Packing dimension
The least value, over countable covers of a set by bounded sets, of the supremum of their upper box-counting dimensions. See Definition 1.1.6.
Packing oracle
An oracle that attains the minimum in the Point-to-Set Principle for packing dimension. See Section 2.4.
Partial bi-computable
Both partial computable and partial co-computable. Abbreviated p.b.c. See Section 1.3.
Partial co-computable
Injective, with a partial computable inverse on its range. Abbreviated p.c.c. See Section 1.3.
Partial computable function
A partial function computed by some Turing machine. Abbreviated p.c. See Section 1.2.
Perfect induction
Induction by Bayes’ Rule using the true prior distribution on hypotheses, i.e., the one governing the source of the observations. See Section 4.1.4.
Plain Kolmogorov complexity
The length C(a∣b)C(a \mid b) of a shortest description of a finitary object aa given bb by the universal machine. See Section 1.3.
Point-to-Set Principle
J. Lutz and N. Lutz’s theorem that the Hausdorff dimension of a set is the least, over all oracles, of the supremum of its points’ effective dimensions relative to that oracle. See Theorem 2.4.1.
Pointwise stability
The property that the effective Hausdorff dimension of a set is the supremum of the effective dimensions of its points. See Section 2.2.
Prefix complexity
The length K(a∣b)K(a \mid b) of a shortest description of a finitary object aa given bb by the universal prefix-free machine; it may be relativized to an oracle. See Section 1.3.
Prefix complexity of a set
The lift of conditional prefix complexity to subsets of Euclidean space, through their rational points. See Section 2.1.
Prefix discrepancy
The gap ΔP⁡ρ(σ):=K(σ)+log⁡ρ([σ])\operatorname{\Delta P}_\rho(\sigma) := K(\sigma) + \log \rho([\sigma]) between a string’s prefix complexity and its mass under a premeasure ρ\rho. See Definition 1.6.1.
Prefix weight
The supremum PW⁡ρ(V)\operatorname{PW}_\rho(\mathcal{V}) of the direct weights of the prefix-free subsets of a collection of strings. See Definition 1.4.1.
Prefix-free
A set of strings no two of which are comparable. See the Notation page.
Prefix-free machine
An oracle machine whose domain is prefix-free for every oracle. See Section 1.3.
Premeasure
A non-negative function on a collection of sets, which also evaluates to zero on the empty set. See Definition 1.1.1.
Preservation set
The set NX(A,B,ε)N_X(A, B, \varepsilon) of points of XX whose complexity relative to AA drops by less than εr\varepsilon r at all but finitely many precisions rr when the oracle BB is added. See Definition 3.1.2.
Random
A sequence is T\mathcal{T}-ρ\rho-random if it passes every test of type T\mathcal{T} for the premeasure ρ\rho; otherwise it is effectively T\mathcal{T}-ρ\rho-null. See Section 1.4.
Randomness
Inscrutability with respect to the tools availabl. E.g., Shannon entropy for all algorithms, Kolmogorov complexity for effective algorithms, epiplexity for roughly polynomial-time ones. See Section 4.1.3.
Rapidly decreasing
A sequence of positive rationals that tends to 0 faster than 2−n2^{-n}. See Section 1.5.
Reasoning
Any procedure for assigning and updating likelihoods to a class of hypotheses. See Section 4.1.1.
Relativization
Generalizing notions or results from Turing machines to oracle machines with an arbitrary oracle. See Section 1.2.
s-set
A set for which the dimension function hs:t↦tsh_s : t \mapsto t^s is an exact gauge; that is, a set XX with 0<Hs(X)<∞0 < \mathcal{H}^s(X) < \infty. See Section 1.1.
Selection
Any procedure for selecting or preferring a hypothesis. See Section 4.1.1.
Solomonoff induction
A method for performing perfect induction over any computable prior probability distribution, using Bayes’ Rule. See Section 4.1.4.
Solovay test
A c.e. set of strings with finite direct weight; a strong Solovay test has finite prefix weight instead. See Definition 1.4.2.
Strong dimension
The effective analogue of packing dimension: defined by the upper incompressibility ratio. See Section 2.2.
Strongly convex premeasure
A premeasure on Cantor space whose value on each one-bit extension of a string is at least half its value on that string. See Section 1.1.
Strongly covers
A sequence of sets strongly covers a set if every element of that set lies in infinitely many of them. See Definition 1.4.4.
Sub-linear term
A term o(r)o(r) that grows more slowly than any positive multiple of rr. See the Notation page.
Subadditivity
The property of a function that its value on a whole is at most the sum of its values on the parts. E.g., prefix complexity is subadditive on pairs up to an additive constant, while outer measures are subadditive on unions. See Section 1.3.
Succeed
A supergale succeeds on a set if its capital is unbounded along every point of that set; a continuous semimeasure ρ\rho-succeeds if its mass outpaces ρ\rho by an unbounded factor along the prefixes of every point. See Section 1.5.
Supergale
A betting strategy that wagers on the successive bits of an infinite binary string, recording its capital after each finite prefix, in a game whose odds are set by a premeasure ρ\rho. See Section 1.5.
Symmetry of information
Another name for the chain rule for prefix complexity. See Theorem 1.3.1.
Total
A partial function defined on the entire space of finitary objects. See Section 1.2.
Turing machine
Turing’s model of computation: a finite program reading and writing symbols on an unbounded tape. By the Church–Turing thesis, the functions Turing machines compute are exactly the intuitively computable ones. See Section 1.2.
Turing reducible
A≤T⁡BA \leq_{\operatorname{T}} B if some oracle machine computes AA from the oracle BB; also called BB-computable. See Section 1.2.
Two-part description
A description of aa by a finite set A∋aA \ni a together with aa’s index in AA, giving K(a)≤K(A)+log⁡∣A∣+O(1)K(a) \leq K(A) + \log \abs{A} + O(1). See Section 1.3.
Uniformly continuous function
A real function with a modulus of uniform continuity. See Section 2.6.
Universal complexity notion
A complexity notion that dominates, simulates, or otherwise approximates an extremal score among a class of complexity notions. See Section 4.1.3.
Universal prior distribution
A lower-semicomputable continuous semimeasure that dominates every other, up to a multiplicative constant. See Section 4.1.4.
Universal Turing machine
A Turing machine computing a universal partial computable function which simulates every other machine. See Section 1.2.
Vehement weight
The infimum of the direct weights of all collections of strings covering the open set generated by a set. See Definition 1.4.1.
Weakly regular
A set whose Hausdorff and packing dimensions are equal. See Definition 1.1.6.