ИИ Google DeepMind самостоятельно вывел и доказал математические закономерности для 11 машин Тьюринга

Исследователи Google DeepMind и Кембриджского университета разработали систему на базе Gemini, которая обнаружила новые математические закономерности в работе 11 машин Тьюринга и формально доказала их корректность. Система не просто анализировала заранее сформулированную математическую задачу, но и выдвигала гипотезы о поведении вычислительных машин, разрабатывала правила для их описания и проверяла доказательства с помощью системы Lean 4.

В результате система вывела и формально подтвердила новые правила для 11 машин из класса BB(6), для которых ранее не было задокументированного анализа.

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

Авторы также получили формальные доказательства похожих правил или новые способы ускорения анализа ещё для 15 машин, которые уже изучались математическим сообществом. Однако исследователи не решили главную загадку этих 11 машин: пока неизвестно, останавливаются ли они. Найденные правила точно описывают их поведение, но не обязательно позволяют определить, закончится ли вычисление. Поэтому авторы предлагают предварительно относить такие экземпляры к категории Cryptids — машин, для которых существует компактное математическое описание работы, но вопрос об остановке остаётся открытым.

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

Подписывайтесь на наш Telegram-канал, чтобы быть в курсе всех новостей и событий Рунета.