Short descriptions of terms defined throughout these notes, each with a link to its full definition.
- A priori complexity
- The complexity of a string, given by the optimal lower-semicomputable continuous semimeasure . See Section 1.5.
- A priori discrepancy
- The gap between a string’s a priori complexity and its mass under a premeasure . See Definition 1.6.1.
- A priori probability
- The total weight of all descriptions of a finitary object under a machine . See Definition 1.5.1.
- Absolutely continuous
- An outer measure is absolutely continuous with respect to , written , if every -null set is -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 given by a finitary object’s shortest description under a machine . See Definition 1.5.1.
- Arithmetic hierarchy
- Kleene’s classification of sets of natural numbers into levels , , 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 , the -th accurate to within ; it is standard if each approximation rounds 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: 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 () 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 computed by an oracle machine that turns any Cauchy representation of an input into a Cauchy representation of its output under . 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 quantifying the asymptotic rate of conditional complexity per bit of precision of given . See Section 2.3.
- Constructive dimension
- J. Lutz’s effective analogue of Hausdorff dimension, : the infimum of such that some constructive -supergale succeeds on . 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, is -conull in if . 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 : the most complex have complexity about , and few strings fall far below it. See Theorem 1.3.5.
- Cover
- A Martin-Löf-type test covers if is a subset of the union of all cover elements; a Solovay-type test covers if each point of has infinitely many prefixes in it. Otherwise passes the test. See Definition 1.4.3.
- Cylinder set
- The set of all infinite binary strings extending a finite string . See the Notation page.
- Dimension function
- A non-negative, non-decreasing, right-continuous function on with exactly when . Also called a gauge. See Section 1.1.
- Direct weight
- The total premeasure 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 for which is Martin-Löf--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 -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 of Cantor space generated by a c.e. set of strings ; a -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 with for a given set . See Section 1.1.
- Expansive map
- A map on Cantor space is -expansive if, for all but finitely many , the first bits of an input determine at least bits of its output. See Section 2.6.
- Extension
- A string extends () if it agrees with on every position of ; a proper extension is one with . See the Notation page.
- Finitary object
- An element of a standard countable collection such as , , , or , 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 for which a set is null with repect to the -dimensional outer Hausdorff measure. See Section 1.1.
- Hausdorff distance
- The infimum of for which two sets are -close: every point of each lies within of the other. See Section 1.2.
- Hausdorff gauge-regular
- A set with an exact gauge such that matches the Hausdorff dimension of the set. In particular, every -set is Hausdorff gauge-regular. See Section 1.1.
- Hausdorff measure-regular
- A set for which some metric outer measure with has ; that is, deleting a -null set from 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 that applies a dimension function 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 bits of input precision per bit of output precision, where is its exponent; equivalently, output distances are bounded by a constant times the -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 on a collection of finitary objects with . 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 witnessing the minimum complexity ; an -approximate -minimizer has . See Definition 2.1.1.
- Kraft Inequality
- The bound that , 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 that increases in to , witnessing that is lower-semicomputable. See Section 1.2.
- Length-invariant
- A premeasure on Cantor space whose value on depends only on . See Section 1.1.
- Lightface Borel hierarchy
- The effective hierarchy of -, -, and -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 and 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 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 of sets of strings, each of which having direct weight at most ; strong and vehement versions bound the prefix or vehement weight instead. See Definition 1.4.2.
- Method II outer measure
- Rogers’s outer measure induced by a premeasure , using covers of diameter at most (the -contents ) and letting . See Section 1.1.
- Minimal description
- A description of a finitary object (given ) of the least possible length; any with is an -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 telling how much input precision suffices for a desired output precision: inputs within of each other have outputs within . See Definition 2.6.1.
- Mutual dimension
- Case and Lutz’s lower and upper mutual dimensions and : the asymptotic rates of mutual information per bit of precision shared by and . See Section 2.3.
- Mutual information
- The algorithmic information shared by finitary objects, lifted to sets and to reals at given precision-levels. See Section 2.3.
- Neighborhood
- The -neighborhood of a subset of a metric space consists of all points within distance of that subset. See the Notation page.
- Null set
- A set of outer measure zero. In particular, -null means , and -null means . 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., and 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 for such that, for every oracle and , some has and for all but finitely many . See Definition 3.1.1.
- Optimal packing oracle
- The packing analogue of an optimal Hausdorff oracle, using packing oracles, , and . 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 of a shortest description of a finitary object given 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 of a shortest description of a finitary object given 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 between a string’s prefix complexity and its mass under a premeasure . See Definition 1.6.1.
- Prefix weight
- The supremum 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 of points of whose complexity relative to drops by less than at all but finitely many precisions when the oracle is added. See Definition 3.1.2.
- Random
- A sequence is --random if it passes every test of type for the premeasure ; otherwise it is effectively --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 . 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 is an exact gauge; that is, a set with . 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 that grows more slowly than any positive multiple of . 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 -succeeds if its mass outpaces 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 . 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
- if some oracle machine computes from the oracle ; also called -computable. See Section 1.2.
- Two-part description
- A description of by a finite set together with ’s index in , giving . 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.