The Kolmogorov complexity (also known as algorithmic complexity and algorithmic entropy) of an object is the length of the shortest program that generates it.
ββββββββββββββ KOLMOGOROV COMPLEXITY ANALYZER ββββββββββββββββββ
β Measuring Minimal Program Length β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β β
β Example Analysis: β
β βββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Input String: "AAAAAAAAAA" β β
β β β β
β β Program 1: print("AAAAAAAAAA") // len: 20 β β
β β Program 2: print("A" * 10) // len: 14 β β
β β Program 3: for(i=0;i<10;i++)print(A)// len: 22β β
β β β β
β β K(x) = 14 bits β β
β βββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Complexity Spectrum: β
β βββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Random: High K(x) ββββββββββ β β
β β Mixed: Medium K(x) βββββ β β
β β Ordered: Low K(x) β β β
β βββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Program Length vs. Output Length: β
β βββββββββββββββββββββββββββββββββββββββββββββββββ β
β βLengthβ β β
β β ^ β Random Data β β
β β β β β± β β
β β β β β± β β
β β β β β± Pattern β β
β β β β β± β β
β β β ββββββββββββββββββββββββ> Output Size β β
β βββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β Incompressibility Principle: β
β βββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Input: "4c7f1q9p2" // Random String β β
β β K(x) β |x| // Cannot compress β β
β β β β
β β Input: "1234567890" // Ordered String β β
β β K(x) << |x| // Can compress β β
β βββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β [Calculate K(x)] [Compare Programs] [Analyze Pattern] β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ