[Перевод] Советский номерной знак и колмогоровская сложность
Физик Лев Ландау играл в ментальную игру с советскими номерами[1]. Таблички имели форму двух цифр, тире, еще двух цифр и некоторых букв.
Правила игры
Его игра заключалась в том, чтобы применять математические операторы к числам по обе стороны от тире, чтобы тире можно было заменить на знак равенства. Например, если взять номерной знак 44–74, одним из решений будет
4! + 4 = 7×4
Обратите внимание, что мы можем вставить операторы, такие как ! , + и *, но не добавляя цифр.
Есть ли решение для каждого возможного номерного знака? Это зависит от того, какие операторы вы разрешаете использовать.
Вы можете тривиализировать игру, применив операцию дробной части { x } к обеим сторонам, поскольку дробная часть целого числа равна нулю. Вы можете запретить оператор дробной части на том основании, что это явно не математическая операция старшей школы, или просто запретить ее, потому что она делает игру неинтересной.
Перевод выполнен при поддержке компании EDISON Software, которая инвестирует в перспективные стартапы, а так же разрабатывает различные облачные сервисы.
Универсальное решение
Оказывается, есть универсальное решение, начиная с наблюдения, что
√ (n + 1) = sec arctan √ n.
Если одна сторона больше другой на один, формула выше дает немедленное решение. Например, решение для номерного знака 89–88 будет
√89 = sec arctan√88.
Если разница больше, формула может применяться неоднократно. Например, мы могли бы применить формулу дважды, чтобы получить
√ (n + 2) = sec arctan√ (n + 1) = sec arctan sec arctan√ n
и поэтому возможное решение для 35–37 является
sec arctan sec arctan √35 = √37.
Колмогоровская сложность
Учитывая, что решение всегда возможно, мы можем сделать игру более интересной, находя самое простое решение. У нас есть интуитивное представление о том, что это значит. С нашим примером 44–74, первое решение
4! + 4 = 7×4
проще, чем универсальное решение
sec arctan sec arctan… √44 = √74
что потребовало бы применения секансов и арктангенсов 30 раз.
Колмогоровская сложность объекта — это длина самой короткой компьютерной программы для создания объекта. Мы могли бы вычислить колмогоровскую сложность функций, применяемых к цифрам на каждой стороне, чтобы измерить, насколько сложным является решение.
Чтобы выяснить это, нам нужно указать, какой у нас язык программирования, и это не так просто, как кажется. Если мы думаем о математической нотации как о языке программирования, хотим ли мы считать! как один символ и arctan как 6 символов? Это не кажется правильным. Если бы мы написали «arctan» как «atn», мы бы использовали меньше символов, не создавая другого решения.
Сложность кода Python
Чтобы сделать вещи более объективными, мы могли бы рассмотреть длину реальных компьютерных программ, а не представлять математическую нотацию как язык программирования. Скажем, мы выбрали Python. Тогда вот пара функций, которые вычисляют наши два решения для номерного знака 44–74.
from math import sqrt, cos, atan
def f():
sec = lambda x: 1/cos(x)
y = sqrt(44)
for _ in range(30):
y = sec(atan(y))
return y
def g():
return sqrt(77)
Мы могли бы измерить сложность наших функций f и g подсчитывая количество символов в каждой. Но все еще есть трудности.
А как насчет импорта? Его длина должна считаться с f потому что он использует все импортированные операторы, но g использовал более короткий оператор, который только импортировал sqrt. Более фундаментально, мы обманываем, даже импортируя библиотеку?
Кроме того, две вышеупомянутые функции не дают точно такой же результат из-за ограниченной точности. Мы можем представить, что наши импортированные функции бесконечно точны, но тогда мы на самом деле не используем Python, а скорее идеализированную версию Python.
А как насчет цикла? Это ввело новые цифры, 3 и 0, и поэтому нарушает правила игры Ландау. Так следует ли нам развернуть цикл, прежде чем вычислять сложность?
Мысленный эксперимент
Сложность по Колмогорову — очень полезная концепция, но это скорее мысленный эксперимент, чем то, что вы можете вычислить практически. Мы можем представить себе самую короткую программу для вычисления чего-либо, но мы редко можем знать, что мы действительно нашли такую программу. Все, что мы можем знать на практике, это верхние границы.
Теоретически вы можете перечислить все машины Тьюринга заданной длины или все программы Python заданной длины и найти самую короткую, которая выполняет данную задачу, но список растет экспоненциально с увеличением длины.
Тем не менее, можно рассчитать продолжительность конкретных программ, если мы имеем дело с некоторыми из упомянутых выше сложностей. Мы могли бы сделать игру Ландау игрой для двоих, посмотрев, кто может предложить более простое решение за фиксированный промежуток времени.
Вернемся к Ландау
Если мы допустим синус и степень в нашем наборе операторов, то у Б.С. Горобец есть универсальное решение. Для n ≥ 6, n! кратный 360, и так
sin (n!) ° = 0.
И если n меньше 6, его двузначное представление начинается с нуля, поэтому мы можем умножить цифры, чтобы получить ноль.
Если мы запрещаем трансцендентные функции, мы блокируем трюк Горобец и у нас есть функции, длину которых мы можем объективно измерить на языке программирования.
