Complexity-2
The low complexity binary strings are very rare!
A consequence of the above analysis is that the complexity of 99% of the binary strings of length N is grater than N-7.
An excess of 0 or 1 is a trace for contained complexity:
If the number of 1 in a binary sequence x of length N is K, then:
Relationship between and Shannon’s Entropy
Shannon Entropy is a computable upper bound for algorithmic complexity.
Information between two strings
The definition, somehow similar to the statistical mutual information, is:
I(y:x) = K(x) – K(x/y)
It is a non-commutative function.
How random is a string
Consider a string x belonging to the finite set D. The deficiency of randomness of x with respect to D is:
D(x/D) = log #D-K(x/D)
Prefix Complexity
A partial recursive function F(p,y) is called a prefix with respect with respect to the first argument if:
F(p,y)=F(p’,y) if pÍp’ and (p,y) and (p’,y) belong to the domain of F. y is a parameter.
One can define a prefix complexity
KP(x/y) = min[ l(p): F(p, y) = x]
It can be shown that there exists an optimal recursive function. There exists a relationship between prefix complexity and Kolmogorov complexity:
Solomonoff ‘s Algorithmic Probability
We try here to sketch Solomonff’s theory of algorithmic complexity [1]. The original is much more complex and make use of probabilistic grammar theory, introduced by Solomonoff himself. We apologize for the necessary simplifications to make the concept affordable in a reasonable short time.
We define first the uniform probability of a given binary string x of N digits.
It can be identified with the infinite string:
101001011010010111010****************************************************************
where the first N digits are defined, while the rest is represented by *, meaning that the values of the bits N+1, N+2,….. can have whatever value.
The probability of such a string is
As binary strings can be identified with programs p, we can write:
Here l(p) represents the length of the program.
Let’s consider a given binary string x and a UTM. We know that there exist many (infinite) strings p that can satisfy the relation:
UTM(p)=x
Let us consider the set [p: UTM(p)=x]. We can interpret each program of such a set as a possible deterministic process underlying the string x production. Therefore, intuitively, the sum of the probabilities of all the strings of the above set represents the realistic “plausibility” of the string x. One can conclude that:
as a measure of the plausibility of x, or “algorithmic probability”.
The above equation is clearly a diverging one, and has given rise to many attempts of normalisation, which will not be discussed here.
As Kolmogorov complexity gives the order of magnitude of the largest term of the sum on the rhs of the above definition, an approximated form can be adopted:
ignoring smaller terms.
References
[1] Solomonff R., (1978), Complexity based induction systems: comparison and convergence theorems, IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-24, NO. 4, pp:422-432
Next Page