Kolmogorov Complexity in perspective. Part II: Classification, Information Processing and Duality

Details Kolmogorov Complexity in perspective. Part II: Classification, Information Processing and Duality Kolmogorov Complexity in perspective. Part II: Classification, Information Processing and Duality

2010-10-13

arxiv.org/abs/1010.2595v1

Synthese / Synth\`ese (2010) 00

Computer Science

Logic in Computer Science

43 pages

Scientific paper

We survey diverse approaches to the notion of information: from Shannon entropy to Kolmogorov complexity. Two of the main applications of Kolmogorov complexity are presented: randomness and classification. The survey is divided in two parts published in a same volume. Part II is dedicated to the relation between logic and information system, within the scope of Kolmogorov algorithmic information theory. We present a recent application of Kolmogorov complexity: classification using compression, an idea with provocative implementation by authors such as Bennett, Vitanyi and Cilibrasi. This stresses how Kolmogorov complexity, besides being a foundation to randomness, is also related to classification. Another approach to classification is also considered: the so-called "Google classification". It uses another original and attractive idea which is connected to the classification using compression and to Kolmogorov complexity from a conceptual point of view. We present and unify these different approaches to classification in terms of Bottom-Up versus Top-Down operational modes, of which we point the fundamental principles and the underlying duality. We look at the way these two dual modes are used in different approaches to information system, particularly the relational model for database introduced by Codd in the 70's. This allows to point out diverse forms of a fundamental duality. These operational modes are also reinterpreted in the context of the comprehension schema of axiomatic set theory ZF. This leads us to develop how Kolmogorov's complexity is linked to intensionality, abstraction, classification and information system.

Affiliated with

Also associated with

No associations

Rating

Kolmogorov Complexity in perspective. Part II: Classification, Information Processing and Duality does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Kolmogorov Complexity in perspective. Part II: Classification, Information Processing and Duality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kolmogorov Complexity in perspective. Part II: Classification, Information Processing and Duality will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-226257