Why do you say that Kolmogorov complexity isn’t the right measure?
most uniformly sampled programs of equal KC that produce a string of equal length.
...
“typical” program with this KC.
I am worried that you might have this backwards?
Kolmogorov complexity describes the output, not the program. The output file has low Kolmogorov complexity because there exists a short computer program to describe it.
Let me rephrase then: most strings of same length and same KC will have much more intuitively complex programs-of-minimum-length that generated them.
Why is the program intuitively simple? Well for example, suppose you have the following code in the else block:
a.append(min(max(int(i+a[i]),2),i)
i += 1
I think the resulting program has lower length (so whatever string it generates has lower KC), but it would be way harder to find. And I bet that a uniformly sampled string with the same KC will have a program that looks much worse than that. The kinds or programs that look normal to you or me are a heavily skewed sample, and this program does look reasonably normal.
Eh. I agree with both replies that the example was bad. I wanted to do something unintuitive with pointer arithmetic, but the particular code probably doesn’t capture it well, so it may in fact be easier to find. (Still totally stand by the broader point though.)
Why do you say that Kolmogorov complexity isn’t the right measure?
I am worried that you might have this backwards?
Kolmogorov complexity describes the output, not the program. The output file has low Kolmogorov complexity because there exists a short computer program to describe it.
Let me rephrase then: most strings of same length and same KC will have much more intuitively complex programs-of-minimum-length that generated them.
Why is the program intuitively simple? Well for example, suppose you have the following code in the
elseblock:a.append(min(max(int(i+a[i]),2),i)i += 1I think the resulting program has lower length (so whatever string it generates has lower KC), but it would be way harder to find. And I bet that a uniformly sampled string with the same KC will have a program that looks much worse than that. The kinds or programs that look normal to you or me are a heavily skewed sample, and this program does look reasonably normal.
I don’t think this follows—your code is shorter in python but it includes 3 new built in functions which is hidden complexity.
I do agree with the general point that KC isn’t a great measure of difficulty for humans—we are not exactly arbitrary encoders.
Why do you think that “would be way harder to find”? (My intuition goes exactly the other way.)
Eh. I agree with both replies that the example was bad. I wanted to do something unintuitive with pointer arithmetic, but the particular code probably doesn’t capture it well, so it may in fact be easier to find. (Still totally stand by the broader point though.)