Kolmogorov complexity

J. L. Balcazar, R. Gavalda, and H. T. Siegelmann, Computational power of neural networks a Kolmogorov complexity characterization, IEEE Trans. Inf. Theory 1991). 

As noted, Kolmogorov complexity has been suggested as a method for measuring specification. The novelty in the method presented here is the use of conditional Kolmogorov complexity. However, this paper also elucidates a number of examples of algorithmic compressibility demonstrating wider applicability than is often realized. 

Kolmogorov complexity is a method of measuring information. It is defined as the minimum length computer program, in bits, required to produce a binary string. 

However, Kolmogorov complexity seems unable to capture the entirety of what is intended by specification. Natural language text is not reducible to a simple pattern however, it is an example of specification. The design of an electronic circuit should also be specified, but it is not reducible to a simple pattern, hi fact, the cases of specification that Kolmogorov complexity seems able to capture are limited to objects which exhibit some very simple pattern. But these are not the objects of most interest in terms of specification. 

There is also an extension of Kolmogorov complexity known as conditional Kolmogorov complexity which can be used (Kolmogorov, 1968a). With conditional Kolmogorov complexity, the program now has access to additional data as its input. 

For this number to become large requires X to be both complex (i.e., improbable) and specified (i.e., compressible). Failing on either of these counts will produce a low or negative value. Since Kolmogorov complexity can, at best, be upper bounded, the ASC can, at best, be lower bounded. 

Kolmogorov complexity is not limited to exploiting what humans perceive as simple patterns. It can also capture other aspects such as functionality. Functionahty can be described as passing a test. As a result, functional objects are compressible. 

However, in order to actually give a bound for Kolmogorov complexity, the length of the computer program which interprets the bits must also be included. Here is an example computer program in Python which could interpret the message... 

Given different choices of L and N, this program will output any particular folding protein. This means that the protein can be described by providing those two numbers. Thus, the conditional Kolmogorov complexity can be calculated using these two numbers. 

Any element x can be described given the probability distribution and logf x) bits. Given that f x) and F can be calculated with a constant program, the conditional Kolmogorov complexity can be calculated as... 

It is not possible to calculate the Kolmogorov complexity of an object. However, it is possible to upper-bound the Kolmogorov complexity and thus lower-bound the algorithmic specihed complexity. This means that something can be determined to be at least this specihed, although the possibility that it is even more specihed cannot be ruled out. Therefore, even though detecting a specihcation cannot be achieved mechanically, it can be objectively identihed when found. 

In statistics, the complexity of a signal, say, y, = W X (the temporal index is made implicit), is rigorously measured by Kolmogorov complexity. Given that Kolmogorov complexity is not intuitive and difficult to approximate in practice. Stone (2001, 2004) provided a simple yet robust complexity measure of a signal, temporal predictability, which is defined by... 

---