Search Results

This chapter develops the theory of plain Kolmogorov complexity, and then of prefix-free Kolmogorov complexity. A main technical tool for later chapters is the Machine Existence (or Kraft–Chaitin) Theorem. The chapter uses some probability theory to obtain statistical properties of incompressible strings.

A computational theory of meaning tries to understand the phenomenon of meaning in terms of computation. Here we give an analysis in the context of Kolmogorov complexity. This theory measures the complexity of a data set in terms of the length of the smallest program that generates the data set on a universal computer. As a natural extension, the set of all programs that produce a data set on a computer can be interpreted as the set of meanings of the data set. We give an analysis of the Kolmogorov structure function and some other attempts to formulate a mathematical theory of meaning in terms of two-part optimal model selection. We show that such theories will always be context dependent: the invariance conditions that make Kolmogorov complexity a valid theory of measurement fail for this more general notion of meaning. One cause is the notion of polysemy: one data set (i.e., a string of symbols) can have different programs with no mutual information that compresses it. Another cause is the existence of recursive bijections between ℕ and ℕ2 for which the two-part code is always more efficient. This generates vacuous optimal two-part codes. We introduce a formal framework to study such contexts in the form of a theory that generalizes the concept of Turing machines to learning agents that have a memory and have access to each other’s functions in terms of a possible world semantics. In such a framework, the notions of randomness and informativeness become agent dependent. We show that such a rich framework explains many of the anomalies of the correct theory of algorithmic complexity. It also provides perspectives for, among other things, the study of cognitive and social processes. Finally, we sketch some application paradigms of the theory.

The principle of Kolmogorov minimal sufficient statistic (KMSS) states that the meaningful information of data is given by the regularities in the data. The KMSS is the minimal model that describes the regularities. The meaningful information given by a Bayesian network is the directed acyclic graph (DAG) which describes a decomposition of the joint probability distribution into conditional probability distributions (CPDs). If the description given by the Bayesian network is incompressible, the DAG is the KMSS and is faithful. The chapter proves that if a faithful Bayesian network exists, it is the minimal Bayesian network. Moreover, if a Bayesian network gives the KMSS, modularity of the CPDs is the most plausible hypothesis, from which the causal interpretation follows. On the other hand, if the minimal Bayesian network is compressible and is thus not the KMSS, the above implications cannot be guaranteed. When the non‐minimality of the description is due to the compressibility of an individual CPD, the true causal model is an element of the set of minimal Bayesian networks and modularity is still plausible. Faithfulness cannot be guaranteed though. When the concatenation of the descriptions of the CPDs is compressible, the true causal model is not necessarily an element of the set of minimal Bayesian networks. Also modularity may become implausible. This suggests that either there is a kind of meta‐mechanism governing some of the mechanisms or a wrong model class is considered.

Attempts to measure grammatical complexity are often based on data from a subset of properties in a language as an approximation. Despite this, such a subset of core grammatical phenomena is not representative of the language as a whole, and in such an approximation many properties that would add to complexity are easily overlooked. A case study of English try and pseudocoordination (I will try and win the race!) provides evidence for this claim. In this construction, neither verb can be inflected, and it is shown that there must be explicit reference to inflection in the syntactic derivation, a property not found more generally in the language. This is exactly the sort of linguistic phenomenon that would be easily overlooked by researchers selecting a purportedly representative sample. Therefore, it is concluded that accurate measurement of grammatical complexity must be based on extensive, preferably exhaustive, description of a linguistic system.

The parsimony method for reconstruction of evolutionary trees (Sober, 1988) and the minimal edit distance method for DNA sequence alignments (e.g., Waterman, 1984) are both based on the principle of Occam’s Razor (e.g., Losee, 1980; also known as the Parsimony principle). This principle favors the most concise theories among the multitudes that can possibly explain observed data. The conciseness may be measured by the number of postulated mutations within an evolutionary tree, by the number of edit operations that transform one DNA sequence into the other, or by another implicit or explicit criterion. A very general mathematical formulation of Occam’s Razor has been proposed via minimal length encoding by computer programs (for recent reviews, see Cover and Thomas, 1991; Li and Vitányi, 1993). Algorithmic significance is a general method for pattern discovery based on Occam’s Razor. The method measures parsimony in terms of encoding length, in bits, of the observed data. Patterns are defined as datasets that can be concisely encoded. The method is not limited to any particular class of patterns; the class of patterns is determined by specifying an encoding scheme. To illustrate the method, consider the following unusual discovery experiment: . . . 1. Pick a simple pseudorandom generator for digits from the set {0, 1, 2, 3}. 2. Pick a seed value for the generator and run it to obtain a sequence of 1000 digits; convert the digits to a DNA sequence by replacing all occurrences of digit 0 by letter A, 1 by G, 2 by C, and 3 by T. 3. Submit the sequence to a similarity search against a database containing a completely sequenced genome of a particular organism. . . . Assume that after an unspecified number of iterations of the three steps, with each iteration involving a different random generator or seed value or both, the search in the third step finally results in a genomic sequence highly similar to the query sequence. Does the genomic sequence contain a pattern? To argue for the presence of a pattern, one may directly apply the algorithmic significance method.