Busy beaver hunters reach numbers that overwhelm ordinary math
Что такое «Busy Beaver»
Функция Σ(n) показывает максимальное количество 1, которое может оставить на ленте останавливающаяся машина Тьюринга с n состояниями и двумя символами (0 и 1). Аналогично, S(n) — максимальное число шагов до остановки. Оба значения растут быстрее любой вычислимой функции, поэтому уже Σ(5) и S(5) неизвестны без компьютерного перебора.
Новый рекорд: n = 6
Команда «Beaver Hunters» (Scott Aaronson, Shawn Ligocki et al.) доказала:
- S(6) = 36 534 678 263 377 ≈ 3,65 × 10¹³
- Σ(6) = 10 ↑↑ 15
(15-я степень десятки в стеке степеней: 10^(10^(10^…)))
Это число настолько велико, что его нельзя записать в обычной десятичной форме: для этого потребовалось бы больше атомов, чем во Вселенной.
Как нашли
- Использовали SAT-решатели и распределённые вычисления, чтобы перебрать ~10⁴⁴ машин.
- Для оставшихся «подозрительных» случаев построили индивидуальные доказательства остановки или бесконечного цикла.
- Работа заняла ~2 года и миллионы часов CPU.
Зачем это нужно
- Busy Beaver служит «натуральной» границей между вычислимым и не-вычислимым.
- Новые методы перебора и доказательств могут пригодиться в верификации ПО и теории сложности.
- Следующая цель — n = 7, но она потребует принципиально новых идей и, вероятно, ещё более фантастических чисел.