The Soviet license plate game and Kolmogorov complexity

And, of course, one must always ask what is the least number of bits required to explain Kolmogorov complexity.

Huh, I thought I was the only one playing this weird game in my head. I used to live in a country where license plates are all numeric digits. But with 4 digits and my limited knowledge of math operations (I was a child), it was hard to find plates that "had solutions". So I gave myself a little wiggle room by imagining the numbers were written as they were on digital alarm clocks, where certain numbers (like {2,3,5} and {6,9}) required the same number of "bars" to represent [1]. I added a rule that the bars can be rearranged to form different numbers (e.g. 2, 3 and 5 can be rearranged as each other).

Eventually, I added another rule that allowed the bars to be "concatenated," for example, "1" with two bars and "2" with 5 bars can be added to form "8", which requires 7 bars.

[1] https://goo.gl/images/t2njyy

Doesn't this just kick the problem down the road? Now you've introduced the optimisation of the compiler abd the expressiveness of your processor's machine language. The problem of knowing you have the "best" solution remains.

I think if you are trying to come up with a canonical languahe to measure kolmogorov complexity in you can do better, like Binary Lambda Calculus.

https://tromp.github.io/cl/LC.pdf

The issue with trying to apply Kolmogorov complexity to extremely small data (4 digits here) is that the universal Turing machine itself might take more than 4 digits to write down. In principle, one could extend it to any sufficiently long pair of n digits, and then the question would be mathematically robust (though still uncomputable).

Also, for what it's worth, for large enough n, probably there are no interesting short answers. C(x|y) - the conditional complexity of any string x given any other string y is close to maximum (approximately the length of x) for most pairs x and y. This means, for most pairs x and y, there will be no simple short equations connecting x to y, regardless of the mathematical operators we take.

The problem of complexity is solved neatly in Prolog and Erlang¹, by counting “reductions”. For simple tasks like in the article,

one function call ≅ one reduction.

Loops? There are no loops in Erlang, they are usually tail-recursive function calls.

¹) in Erlang it plays a very important role because the VM uses that information for scheduling.