Conditional Kolmogorov Complexity

Proposed Information Metric: Conditional Kolomogorov Complexity

Winston Ewert and Robert J. Marks (Baylor University)

As engineers we would like to think that we produce something different from that of a chaotic system. The Eiffel tower is fundamentally different from the same components lying in a heap on the ground. Mt. Rushmore is fundamentally different from a random mountainside. But we lack a good method for quantifying this idea. This has led some to reject the idea that we can detect engineered or designed systems. Various methods have been proposed each of which has various faults. Some have trouble distinguishing noise from data, some are subjective, etc. We propose to use conditional Kolmogorov complexity to measure the degree of specification of an object. The kolmogorov complexity of an object, is the length of the computer program required to describe that object. Conditional Kolmogorov complexity is Kolmogorov complexity, but also gives access to a context. The program can extract information from the context in a variety of ways allowing more compression. The more compressible an object is the more we may deem the object specified. Random noise is in-compressible, and so compression indicates that the object is not simply random noise. This measurement has several advantages. It includes many previous methods as special cases. It capture the notion of information depending on a context, i.e. Spanish text carries no information for a English speaker. It also captures the notion that we cannot mechanically detect information, but we can identify it when it is there.