# What are a set of example of tasks or problems where the Kolmogorov Complexity is Known -- ideally numerical values can be obtained?

Is there a machine learning task (or any task/problem) that one can by construction know the Kolmogorov Complexity (or minimum description length)? I know the Kolmogorov Complexity is uncomputable but I was curious if there existed a set of tasks that the Kolmogorov Complexity can be known apriori and one can vary the Kolmogorov Complexity of those related tasks. I know Kolmogorov Complexity is uncomputable but I thought perhaps if it was by construction known then the task described -- perhaps it was doable.

Some ideas I thought of:

1. Random bitstrings: As mentioned before, the Kolmogorov complexity of a fair coin flip bitstring of length n is exactly n. No shorter description is possible.
2. Lookup tables: If you construct a lookup table that maps n-bit input binary strings to arbitrary outputs, the table requires 2^n entries, each of b bits. So the total complexity is 2^n * b.
3. Parity functions: As you mentioned, an n-bit parity function requires describing each of the n input bits, so the complexity is n. More formally, you need n + c bits where c is the size of the program that computes XOR. For large n, c is negligible.
4. Decision tree models: If you construct a full binary decision tree of depth d, it has 2^d leaves. To specify it requires 2^d output class labels + internal node conditions. Each condition can be specified in c bits. So total complexity is roughly c2^d.

Ideally I want to implement it in a computer to create this family of known Kolmogorov Complexity problems.

fyi: uncomputable means that there is no algorithm to compute it in general and I know KC is uncomputable in the general case.

• The Kolmogorov complexity is uncomputable but "... von oben rekursiv aufzählbar." -- This hint found in German Wikipedia is missing in the French and Enghlish version. So, good luck. BTW, what the hell will you do with this information? What does it help in real world? Feb 3 at 7:16
• @m-stgt uncomputable means that there is no algorithm to compute it in general. But it's easy to compute it for say a totally uniform random string of size n. It's n. specifying the string. I'd like to correlate it with computable measures of complexity of tasks. Feb 5 at 5:43
• @m-stgt fields like formal methods deal with uncomputable problems all the time. They reason by specific case usually and they have drawbacks. I'm not looking for a general algorithm :) Feb 5 at 5:44
• "know the Kolmogorov Complexity" of what? I'm a bit lost by what you're asking, what string you want to know the KC of, and how that is supposed to be related to a ML problem. What do you mean by the KC of a "task"? Can you edit your post to formulate the problem statement more clearly/explicitly?
– D.W.
Feb 10 at 8:17
• "the Kolmogorov complexity of a fair coin flip bitstring of length n is exactly n" - This is not correct. The KC of a string depends on the string, not on how it was chosen. The KC of a string chosen by flipping a fair coin n times is no greater than n, but it could be smaller. For instance, TTTTTT..TTT is a possible outcome, and its KC is a constant. There seem to be some misconceptions in the question about KC.
– D.W.
Feb 10 at 8:19

As m-stgt found, the complexity is "recursively enumerable from above," which is to say there is a recursively enumerable decreasing sequence of functions that approaches the complexity function $$K(s)$$. The method, due to Kolmogorov, is however not enlightening and terminates on no inputs: Let the sequence $$K_t(s)$$ be indexed by natural $$t$$, and let $$K_0(s)$$ be a naïve upper bound on the complexity of $$s$$. Then, to find $$K_{t+1}(s)$$, run all Turing machines with descriptions shorter than $$K_t$$ for $$t$$ steps, and take $$K_{t+1}(s)$$ to be the minimum of $$K_t(s)$$ and the description lengths of any Turing machine that outputs $$s$$. This is obviously decreasing in $$t$$, and as $$t\rightarrow\infty$$ you have $$K_t(s)\rightarrow K(s)$$. This computes the complexity in the same sense that running all Turing machines of a certain length increasingly longer computes the busy beaver function: eventually you'll have the answer, but the tricky bit is knowing when you have it.