Workshop: Information-Theoretic Principles in Cognitive Systems

There Are Fewer Facts Than Words: Communication With A Growing Complexity

Lukasz Debowski


We present an impossibility result, called a theorem about facts and words, which pertains to a general communication system. The theorem states that the number of distinct words detectable in a finite text cannot be less than the number of independent elementary persistent facts described in the same text. In particular, this theorem can be related to Zipf's law, power-law scaling of mutual information, and power-law-tailed learning curves. The assumptions of the theorem are: a finite alphabet, linear sequence of symbols, complexity that does not decrease in time, entropy rate that can be estimated, and finiteness of the inverse complexity rate.

Chat is not available.