I wish to compare compressors using strings with known Kolmogorov Complexity, but I haven't got the theoretical background and tools to understand how to do that. I'm just starting in this area and any pointer to papers/textbooks is highly appreciated.
I imagine that to "tune" the KC of a string with length $n$, one has to use some random source, otherwise the same program used to generate several strings could be used as the measure of complexity for those strings. I idealized a state machine with two states (A and B, starting state = A) and a transition probability $p$ that would produce the following strings with different complexities for different $p$:
p = 0.0: AAAAAAAAAAAAAAAAAAAAAAAAAA... KC ~ 1: = A * n p = 0.1: AAAAAABBBBBAAAAAAAAAAAABBB... KC ~ n/10?: = (A * 6) ++ (B * 5) ++ (A * 12) ++ ... p = 0.5: AABBABABBBBBBAAABBABBBABBBA... KC = n? p = 0.9: ABABAABABABABABBABABABABAA... KC ~ n/10?: = (AB * 2) ++ A ++ (AB * 5) ++ B ++ (AB * 4) ++ ... p = 1.0: ABABABABABABAABABABABABABA... KC ~ 1: = AB * (n/2)
However, this look like more some measure of entropy than proper KC. Are they equivalent for randomized processes?