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.
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.
