André Nies
- Published in print:
- 2009
- Published Online:
- May 2009
- ISBN:
- 9780199230761
- eISBN:
- 9780191710988
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199230761.001.0001
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic ...
More
The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts and methods originating from randomness enrich computability theory. The book is about these two aspects of sets of natural numbers and about their interplay. For the first aspect, lowness and highness properties of sets are introduced. For the second aspect, firstly randomness of finite objects are studied, and then randomness of sets of natural numbers. A hierarchy of mathematical randomness notions is established. Each notion matches the intuition idea of randomness to some extent. The advantages and drawbacks of notions weaker and stronger than Martin-Löf randomness are discussed. The main topic is the interplay of the computability and randomness aspects. Research on this interplay has advanced rapidly in recent years. One chapter focuses on injury-free solutions to Post's problem. A core chapter contains a comprehensible treatment of lowness properties below the halting problem, and how they relate to K triviality. Each chapter exposes how the complexity properties are related to randomness. The book also contains analogs in the area of higher computability theory of results from the preceding chapters, reflecting very recent research.Less
The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts and methods originating from randomness enrich computability theory. The book is about these two aspects of sets of natural numbers and about their interplay. For the first aspect, lowness and highness properties of sets are introduced. For the second aspect, firstly randomness of finite objects are studied, and then randomness of sets of natural numbers. A hierarchy of mathematical randomness notions is established. Each notion matches the intuition idea of randomness to some extent. The advantages and drawbacks of notions weaker and stronger than Martin-Löf randomness are discussed. The main topic is the interplay of the computability and randomness aspects. Research on this interplay has advanced rapidly in recent years. One chapter focuses on injury-free solutions to Post's problem. A core chapter contains a comprehensible treatment of lowness properties below the halting problem, and how they relate to K triviality. Each chapter exposes how the complexity properties are related to randomness. The book also contains analogs in the area of higher computability theory of results from the preceding chapters, reflecting very recent research.
André Nies
- Published in print:
- 2009
- Published Online:
- May 2009
- ISBN:
- 9780199230761
- eISBN:
- 9780191710988
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199230761.003.0002
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
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) ...
More
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.Less
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.
Pieter Adriaans
- Published in print:
- 2020
- Published Online:
- December 2020
- ISBN:
- 9780190636685
- eISBN:
- 9780190636722
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780190636685.003.0002
- Subject:
- Economics and Finance, Microeconomics
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 ...
More
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.Less
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.
Jan Lemeire, Kris Steenhaut, and Abdellah Touhafi
- Published in print:
- 2011
- Published Online:
- September 2011
- ISBN:
- 9780199574131
- eISBN:
- 9780191728921
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199574131.003.0027
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
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 ...
More
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.Less
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.
Daniel Ross
- Published in print:
- 2014
- Published Online:
- December 2014
- ISBN:
- 9780199685301
- eISBN:
- 9780191765476
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199685301.003.0010
- Subject:
- Linguistics, Syntax and Morphology, Psycholinguistics / Neurolinguistics / Cognitive Linguistics
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 ...
More
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.Less
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.
Aleksandar Milosavljević
- Published in print:
- 1999
- Published Online:
- November 2020
- ISBN:
- 9780195119404
- eISBN:
- 9780197561256
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780195119404.003.0006
- Subject:
- Computer Science, Systems Analysis and Design
The parsimony method for reconstruction of evolutionary trees (Sober, 1988) and the minimal edit distance method for DNA sequence alignments (e.g., ...
More
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.
Less
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.