Menu
I'm looking for a algorithm that can compute an approximation of the Kolmogorov complexity of given input string. So if K is the Kolmogorov complexity of a string S, and t represents time, then the function would behave something like this.. limit(t->inf)[K_approx(t,S)] = K.
654
If a description d(s) of a string s is of minimal length (i.e., using the fewest bits), it is called a minimal description of s, and the length of d(s) (i.e. the number of bits in the minimal description) is the Kolmogorov complexity of s, written K(s). Symbolically, K(s) = |d(s)|.
Kolmogorov Complexity can be viewed as the ultimate compressor—producing for any arbitrary string (or file or image), a minimum description of that string, given some form of description language.
Kolmogorov complexity isn't computable in the sense that there isn't a single function or Turing machine that will return the complexity of an arbitrary string. A C compressible string can be reduced by C symbols by a compression program. A string that cannot be reduced by even one symbol is said to be incompressible.
Algorithmic complexity is concerned about how fast or slow particular algorithm performs. We define complexity as a numerical function T(n) - time versus the input size n. We want to define time taken by an algorithm without depending on the implementation details.
In theory, a program could converge on the Kolmogorov complexity of its input string as the running time approaches infinity. It could work by running every possible program in parallel that is the length of the input string or shorter. When a program of a given length is found, that length is identified as the minimum length known for now, is printed, and no more programs >= that length are tried. This algorithm will (most likely) run forever, printing shorter and shorter lengths, converging on the exact Kolmogorov complexity given infinite time.
Of course, running an exponential number of programs is highly intractible. A more efficient algorithm is to post a code golf on StackOverflow. A few drawbacks:
53
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
