Hacker News Digest

Ключевое открытие: в июне 2025 г. математики Mark Brittenham и Susan Hermiller опубликовали препринт, в котором впервые опровергли давнюю гипотезу о том, что «число разузлывания» при сложении узлов аддитивно. Их контрпример — это связная сумма тора-узла (2,7) и его зеркального отражения, для которой число разузлывания равно 5, тогда как сумма индивидуальных вкладов равна 3+3=6. Это означает, что в общем случае число разузлывания связной суммы узлов может быть меньше суммы индивидуальных вкладов.

• Обсуждение началось с демонстрации того, что простой узел, который выглядит как тривиальный, на самом деле не является таковым, и что это стало возможным только благодаря компьютерной визуализации.
• Участники затем перешли к философскому вопросу о том, что считается «реальным» в математике: являются ли узлы, числа или другие абстракции чем-то более чем «полезными выдумками».
• Обсуждение затронуло вопрос о том, что может быть «естественным» или «искусственным» в математике, и как эти категории соотносятся с фундаментальными истинами.
• Некоторые участники поделились личными размышлениями о том, как они воспринимают природу математической реальности, и как они думают, что математика может быть или не может быть «реальной».

В шахматах не существует достижимой позиции, где у стороны было бы более 218 ходов. Это доказано компьютерным анализом, подтверждающим композицию гроссмейстера Ненада Петровича 1964 года. Попытки превзойти этот рекорд предпринимались десятилетиями, но все они провалились из-за математических ограничений и огромного количества возможных позиций — примерно 8,7×10^45.

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

• Обсуждение касается статьи о максимальном количестве возможных ходов (218) в достижимой позиции в шахматах, а не о количестве ходов для её достижения.
• Участники уточняют терминологию и выражают признательность Lichess за бесплатные возможности и варианты игры.
• Поднимаются технические вопросы о доказательстве оптимальности решения через решатель Gurobi и методах кодирования шахматных позиций.
• Обсуждается достижимость приведённой в статье позиции и влияние упрощения правил на модель.
• Автор статьи (Tobs40) участвует в обсуждении, поясняя свой метод и подтверждая доказательность результата.

Что такое «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, но она потребует принципиально новых идей и, вероятно, ещё более фантастических чисел.

• Участники обсуждают сверхбольшие конечные числа: Busy Beaver, TREE(3), субкубические графы и быстро-растущие иерархии.
• BB-функция растёт быстрее любой вычислимой функции и не вычислима; для N>549 нельзя доказать в ZFC, что какое-то вычислимое число ≥BB(N).
• Поделились ссылками на видео Numberphile, плейлист Дэвида Мецлера и статью Скотта Ааронсона.
• Появились размышления о том, что делает такие числа интереснее бесконечности, а также о состоянии ленты после остановки BB(5).
• Некоторые критикуют статью Quanta за поверхностное описание экспоненциации и отсутствие объяснения сути BB.