Самоописание программ и колмогоровская сложность

Если различаешь текст программы, её поведение и длину кратчайшего описания, листай до «Теперь сам».

Как думаешь, может ли программа напечатать себя без чтения файла

Можно открыть собственный файл и вывести содержимое, но это зависит от внешнего имени и доступа к файлу. Более интересная программа хранит шаблон и умеет подставить в него описание самого шаблона. Она получает конечный текст, который после запуска печатает ровно этот текст. Такой квин показывает механизм самоописания, но теорема о рекурсии утверждает значительно больше существования одного трюка печати.

На что это похоже

Представь бланк с инструкцией: напечатать бланк, а затем заполнить специальное поле цитатой самого бланка. Не нужно вкладывать бесконечную стопку копий друг в друга: один шаблон и операция цитирования порождают нужную ссылку на своё описание. Различие между исполнением текста и его цитированием останавливает бесконечное разворачивание.

Механизм: неподвижная точка поведения

Пусть T - вычислимый алгоритм, который по описанию программы выдаёт описание другой. Теорема о рекурсии говорит, что найдётся программа P, такая что на каждом входе поведение P совпадает с поведением T(описание P). Совпадение включает расходимость: если одно вычисление не останавливается, соответствующее другое тоже. Сами тексты P и T(P) могут быть совершенно разными.

Это средство доказательств неразрешимости: можно строить программу, действия которой зависят от того, что предполагаемый анализатор сообщает о её собственном описании. Теорема не требует, чтобы произвольная уже написанная программа заранее знала свой текст; она гарантирует существование подходящей конструкции для заданного вычислимого преобразования.

Зафиксируем оптимальную универсальную машину U, в которой симуляция любого другого фиксированного языка добавляет к длине описания лишь постоянный заголовок. Обычная колмогоровская сложность C_U(x) - минимальная длина двоичной программы p, для которой U(p) останавливается и печатает x. В литературе встречается обозначение K и отдельная префиксная версия сложности; здесь используем обычные программы без требования префиксности. Смена универсальной машины меняет сложность не больше аддитивной константы, зависящей от пары машин, а не от строки.

Правило

Самоописание строится конечным цитированием; кратчайшее описание определяется относительно фиксированного языка исполнения. Существование кратчайшей программы не означает существование алгоритма, который её находит. Не смешивай сложность строки с временем выполнения найденного описания.

Разбор: квин и конечная проверка

from contextlib import redirect_stdout
from io import StringIO
from itertools import product

template = "template = %r; print(template %% template)"
source = template % template
buffer = StringIO()
with redirect_stdout(buffer):
    exec(source, {})
printed = buffer.getvalue()
assert printed == source + "\n"
print("Квин совпал с источником:", printed == source + "\n")
print("Символов источника:", len(source))
print("n: строк длины n; описаний короче n")
for n in range(1, 7):
    strings = 2**n
    short = sum(2**length for length in range(n))
    assert short == strings - 1
    print(n, strings, short)
# Перебираем только тексты, не пытаясь решать останов программ.
n = 4
texts = []
for length in range(n):
    for bits in product("01", repeat=length):
        texts.append("".join(bits))
assert len(texts) == 15
assert len(set(texts)) == 15
print("Коротких двоичных текстов при n=4:", len(texts))

Квин совпал с источником: True
Символов источника: 83
n: строк длины n; описаний короче n
1 2 1
2 4 3
3 8 7
4 16 15
5 32 31
6 64 63
Коротких двоичных текстов при n=4: 15

В программе шаблон цитируется через представление строки, а затем подставляется в самого себя. Проверка выполняет построенный текст в отдельном пространстве имён и сравнивает stdout с источником посимвольно. Чтение собственного файла, исходника через introspection и обращения к сети не используются.

Вторая часть - подсчёт возможных описаний, не перебор их выполнения. Всего двоичных строк длины меньше n равно 2ⁿ-1, тогда как строк длины n - 2ⁿ. Каждая останавливающаяся программа печатает не больше одного результата в выбранной модели, поэтому хотя бы одна строка длины n не имеет описания короче n.

Разбор: почему вычислитель сложности невозможен

Предположим, есть алгоритм, точно вычисляющий C_U(x) для любой строки. По числу m перебираем строки в порядке длины и лексикографически, пока не найдём строку сложности больше m. Такая строка существует по подсчёту. Полученный поиск всегда остановится, если предполагаемый вычислитель корректен.

Но найденная строка теперь описана самой программой поиска и двоичной записью m: длина такого описания O(log m) плюс константа. При достаточно большом m она меньше m, противореча выбору строки. Значит точного вычислителя нет. Константа зависит от универсальной машины, но растущий логарифм всё равно проигрывает линейному порогу.

Это не запрещает находить хорошие сжатия отдельных строк. Строка из миллиона нулей имеет короткое описание «повтори ноль миллион раз». А успешный архиватор даёт верхнюю границу сложности через длину архива плюс программу распаковки. Его неудача сжать строку не доказывает несжимаемость всеми возможными программами.

Что ломается без этого

Сравнение размеров двух архивов отвечает о двух алгоритмах кодирования, а не о точной колмогоровской сложности. Ограниченный перебор коротких программ тоже не решает задачу: не остановившийся пока кандидат может остановиться позже. Установив лимит времени, ты меняешь определение на сложность с ресурсным ограничением и должен назвать новое ограничение явно.

Зачем это в работе

Самоописание помогает понимать доказательства границ статического анализа и различать код с данными. Колмогоровская сложность объясняет принципиальный предел универсального сжатия: нельзя гарантированно сокращать все файлы одной длины. Практическая схема сжатия выигрывает на выбранной структуре данных, а на других входах обязана сохранять или увеличивать размер.

Теперь сам

Сколько двоичных программ длины меньше четырёх существует, включая пустую? Почему из этого следует существование четырёхбитной строки без более короткого описания, но не алгоритм её поиска?