Shannon's information(entropy) is the minimum descriptive complexity of a random variable. It doesn't allow us to talk about the information content of a string.
Kolmogorov complexity of a finite object(string) is defined as the length of the shortest program of a universal Turing machine to describe the string. It is the absolute information of a string. If a string has internal structure information and can be compressed, then its Kolmogorov complexity will be smaller than its length. Otherwise it's imcompressible and we call it a random string. But both Shannon's information and Kolmogorov's algorithmic information don't touch the semantics of the string. It seems it is so hard to deal with the meaning of a string mathematically also it would be cool if we could do it. Some references: "An Introduction to Kolmogorov Complexity and Its Applications", Ming Li and Paul Vitanyi (1997) P. Vitanyi, Meaningful information, Proc. 13th International Symposium on Algorithms and Computation (ISAAC'02), Lecture Notes in Computer Science, Vol ???, Springer-Verlag, Berlin, 2002. Chapter 7 of Cover and Thomas' "Elements of Information Theory" ============================================ Haipeng Department of CIS, Kansas State University [EMAIL PROTECTED], [EMAIL PROTECTED] http://www.cis.ksu.edu/~hpguo ============================================ On Mon, 28 Oct 2002, Rizwan Choudrey wrote: > Dear all, > > I wondered if anyone could help with a paradox at the heart of my > understanding of entropy, information and pattern recognition. > > I understand an informative signals as one which contains patterns, as > opposed to radomly distributed numbers e.g. noise. Therefore, I > equate information with structure in the signals distribution. However, > Shannon equates information with entropy, which is maximimum when each > symbol in the signal is equally as likely as the next i.e. a distribution > with no `structure'. These views are contradictory. > > What am I misisng in my understanding? > > Many thanks in advance, > Riz > > > Rizwan Choudrey > Robotics Group > Department of Engineering Science > University of Oxford > 07956 455380 >
