On the Kolmogorov Complexity of Arbitrary Objects

✍ Scribed by Aaron Shenhar

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 795 KB
• Volume: 9
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1006/jcom.1993.1032

✦ Synopsis

The notion of Kolmogorov program-size complexity (or algorithmic information) is defined here for arbitrary objects. Using a special form of recursive topological spaces, called partition spaces, we define a recursive topology which uses a level of partition for approximation of arbitrary objects instead of the usual metric. It is shown that the formulation for arbitrary objects satisfies most of the previous results obtained usually for natural numbers and for sequences of symbols. Thus we claim the existence of abstract computers formalizes the idea that many real-life objects may, in fact, be calculated (or approximated) effectively. We also show the existence of a universal probability measure for our arbitrary objects. O 1993 Academic Press, Inc.