Soviet license plate and Kolmogorov complexity

The physicist Lev Landau played a mental game with Soviet numbers [ 1 ]. The plates had the form of two numbers, a dash, two more numbers and some letters.

Rules of the game

His game was to apply mathematical operators to numbers on either side of the dash so that the dash could be replaced with an equal sign. For example, if you take the license plate 44-74, one of the solutions would be

4! + 4 = 7 * 4

Please note that we can insert operators such as ! , + and * , but without adding numbers.

Is there a solution for every possible license plate? It depends on which operators you allow to use.

You can trivialize the game by applying the fractional part {x} operation to both sides, since the fractional part of the integer is zero. You can prohibit the fractional operator on the grounds that this is clearly not a mathematical operation of high school, or simply prohibit it, because it makes the game uninteresting.

The translation was made with the support of the company EDISON Software , which invests in promising start-ups , as well as develops various cloud services .

Universal solution

It turns out that there is a universal solution, starting with the observation that

√ (n + 1) = sec arctan √ n.

If one side is more than the other one, the formula above gives an immediate solution. For example, the solution for license plate 89-88 would be

√89 = sec arctan√88.

If the difference is greater, the formula can be applied repeatedly. For example, we could apply the formula twice to get

√ (n + 2) = sec arctan√ (n + 1) = sec arctan sec arctan√ n

and therefore a possible solution for 35-37 is

sec arctan sec arctan √35 = √ 37.

Kolmogorov complexity

Given that a solution is always possible, we can make the game more interesting by finding the simplest solution. We have an intuitive idea of ​​what it means. With our example 44-74, the first solution is

4! + 4 = 7 * 4 is

simpler than the universal solution

sec arctan sec arctan ... √44 = √74

which would require the application of secants and arctangents 30 times.

The Kolmogorov complexity of an object is the length of the shortest computer program for creating an object. We could calculate the Kolmogorov complexity of the functions applied to the numbers on each side in order to measure how complex the solution is.

To find out, we need to specify what kind of programming language we have, and this is not as easy as it sounds. If we think of mathematical notation as a programming language, do we want to count! as one character and arctan as 6 characters? It does not seem right. If we wrote “arctan” as “atn”, we would use fewer characters without creating another solution.

Python code complexity

To make things more objective, we could consider the length of real computer programs, rather than presenting mathematical notation as a programming language. Let's say we chose Python. Then here are a couple of functions that compute our two license plate solutions 44-74.

from math import sqrt, cos, atan
    deff():
        sec = lambda x: 1/cos(x)
        y = sqrt(44)
        for _ in range(30):
            y = sec(atan(y))
        return y
    defg():return sqrt(77)

We could measure the complexity of our functions f and g by counting the number of characters in each. But there are still difficulties.

What about imports? Its length must be reckoned with f because it uses all the imported operators, but g used the shorter operator that just imported sqrt. More fundamentally, are we cheating by even importing a library?

In addition, the above two functions do not give exactly the same result due to limited accuracy. We can imagine that our imported functions are infinitely accurate, but then we don’t actually use Python, but rather an idealized version of Python.

What about the cycle? This introduced new numbers, 3 and 0, and therefore violates the rules of the Landau game. So should we unroll the loop before we calculate the complexity?

Thought experiment

Kolmogorov complexity is a very useful concept, but it is more of a thought experiment than what you can calculate in practice. We can imagine the shortest program for calculating something, but we rarely know that we really found such a program. All that we can know in practice is the upper limits.

Theoretically, you can list all Turing machines of a given length or all Python programs of a given length and find the shortest one that performs this task, but the list grows exponentially with increasing length.

However, it is possible to calculate the duration of specific programs if we are dealing with some of the difficulties mentioned above. We could make the Landau game a game for two, seeing who can offer a simpler solution in a fixed amount of time.

Back to Landau

If we allow sine and degree in our set of operators, then B.S. Gorobets have a universal solution. For n ≥ 6, n! is a multiple of 360, and so

sin (n!) ° = 0.

And if n is less than 6, its two-digit representation starts from zero, so we can multiply the numbers to get zero.

If we prohibit transcendental functions, we block the trick of Gorobets and we have functions, the length of which we can objectively measure in a programming language.