Суть открытия: разрыв между сложностью и вероятностью
В алгоритмической теории информации классическая теорема кодирования Левина утверждает, что априорная вероятность события обратно пропорциональна его сложности Колмогорова. Однако новое исследование, проведенное в рамках летней программы PIBBSS 2026 года, доказывает, что для случайных машин остановки (randomized stopping machines) это правило нарушается.
Авторы (Михаил Миронов, Арам Эбтекар, Коул Уайет) показали, что разрыв между стоппинг-сложностью (длиной кратчайшей программы) и априорной вероятностью (суммарным весом всех программ) не ограничен константой. Это означает, что событие может быть объяснено очень простой правилом, но иметь ничтожно малую общую вероятность, так как «масса» вероятности распределена между множеством других, более сложных правил.
Зачем это нужно: Agenda «Золотые наручники» (Golden Handcuffs)
Результат напрямую влияет на архитектуру безопасных универсальных агентов, в частности на концепцию Golden Handcuffs (GH). Идея GH заключается в том, чтобы агент делегировал контроль человеку-наставнику, если он сталкивается с «новыми» событиями, которые могут быть опасными.
- Механизм: Агент должен передавать управление, если триггер остановки имеет низкую сложность (простое правило).
- Проблема: Если теорема кодирования работала бы, то высокая вероятность события означала бы его простоту. Но так как разрыв неограничен, агент может пропустить опасную ситуацию: событие может быть «простым» для детекции, но статистически редким, или наоборот — иметь высокую вероятность, но не быть «простым» в смысле одного конкретного правила.
Кейс: Робот на складе
Авторы приводят пример складского робота, который тысячи раз выполнял рутину. В один день он замечает «короткий путь», который приводит к застреванию конвейера. Момент застревания является новым в точном смысле: существует простое вычислимое правило «остановиться при первом сбое», которое срабатывает именно здесь.
Для универсального априорного распределения эта история объясняется гипотезой, включающей катастрофическое вознаграждение. Робот, оценивая риски, видит, что потенциальная потеря (катастрофа) перевешивает микроскопическую выгоду от ускорения. Он передает управление человеку. После того как человек устранил сбой, правило «первый сбой» больше не работает (сбой становится вторым, третьим), и сложность события растет, позволяя роботу вернуться к оптимизации.
Технические детали и сравнение
Ранее разрыв для подобных понятий (intermediate time complexity) упоминался в работах Вовка и Павловича, ссылавшихся на unpublished manuscript Андреева и Шеня. Данное исследование предоставляет первое доступное, самодостаточное доказательство для префиксных версий.
| Параметр | Классическая теорема кодирования (Левин) | Случайные машины остановки (Новый результат) |
|---|---|---|
| Связь | Вероятность ~ 2-Сложность (с точностью до константы) | Разрыв не ограничен константой |
| Ограничение | Константа C | Ограничено через сложность целого числа K(n) |
| Значение для AI Safety | Простота = Высокая вероятность | Простота ≠ Высокая вероятность (риск ложных срабатываний или пропусков) |
Вклад авторов
Хотя сам факт разрыва не был новостью для узкого круга специалистов, вклад команды AIXI Labs заключается в:
- Предоставлении полного, понятного доказательства (Theorem 1).
- Явном связывании этого математического факта с практической проблемой безопасности ИИ (Golden Handcuffs).
- Демонстрации того, что триггер безопасности GH и интерпретируемая граница сложности не эквивалентны с точностью до аддитивной константы.
Источник: LessWrong ↗