Hacker News Digest

Онлайн-сообщество недавно определило BB(5) = 47,176,870, первый большой прорыв в проблеме "busy beaver game" за 50 лет. Следующая цель - BB(6), но исследователи не ожидают её достижения в ближайшее время из-за программы Antihydra, которая напоминает нерешенную математическую проблему Collatz conjecture.

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

Antihydra представляет особую сложность, так как её поведение тесно связано с проблемой Collatz conjecture, одной из самых известных нерешенных задач в математике. Эта связь делает BB(6) практически недостижимым для точного определения в обозримом будущем.

• Обсуждение охватывает от Busy Beaver до Collatz, от теории вычислимости до философии случайности и даже до SETI@home и Bitcoin, показывая, насколько широко разросся этот меметический вирус.
• Участники обсуждают, как быстро растет функция BB(n), и как она влияет на наше понимание пределов вычислимости и случайности.
• Обсуждается, что даже если бы мы знали BB(5) или BB(6), это бы не дало нам практического способа вычислить BB(6) или выше; вопрос остаётся открытым, что делает эту область столь интригующей.
• Участники также затрагивают вопрос о том, как публикация в блогах может влиять на восприятие этой темы и как можно было бы лучше донести эти идеи до широкой аудитории.
• В конце обсуждение смещается к тому, что даже если бы мы могли бы вычислить эти числа, мы бы всё равно не могли бы их сравнить с чем-то, потому что они бы оказались слишком большими, чтобы иметь какое-либо значение в контексте чего-либо, кроме как самоограничения.

Big O — способ описать, как время работы функции растёт с ростом входных данных, без привязки к конкретным секундам.

Рассмотрим 4 основные категории:

---

O(n) — линейное время

function sum(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

• sum(1e9) ≈ 1 с
• sum(2e9) ≈ 2 с
  Время пропорционально n.

---

O(1) — константное время

function sum(n) {
  return (n * (n + 1)) / 2;
}

• sum(1e9) и sum(100e9) выполняются почти мгновенно.
  Время не зависит от n.

---

Ключевые идеи

• O = «order of growth»; описывает рост, а не абсолютное время.
• O(1) ≠ «быстро», а «не растёт с размером входа».
• При достаточно большом n O(1) всегда обгонит O(n).

• Обсуждение статьи о нотации Big O разделилось на «лайтовое» восхищение визуализациями и «экспертные» споры о точности определений.
• Новички признаются, что статья впервые открыла им глаза на сложность алгоритмов, а ветераны IT спорят, что за 40 лет ни разу не пригодилась.
• Критика сводится к тому, что автор описывает «поп-культурный» вариант Big O, путая его с Θ-нотацией и worst-case.
• Практики напоминают: на реальном железе константы, кэш и NUMA могут перечеркнуть асимптотику, а O(n²) при малых n часто быстрее «константного» хэша.
• Люди делятся шпаргалками (bigocheatsheet.com, visualgo.net) и просят ещё интерактивных уроков.

Предложен детерминированный алгоритм времени O(m log^{2/3} n) для задачи кратчайших путей из одного источника (SSSP) во взвешенных ориентированных графах с неотрицательными весами в модели сравнение-сложение. Впервые превзойдена граница O(m + n log n) алгоритма Дейкстры на разреженных графах, что доказывает его неоптимальность для SSSP.

• Обсуждали статью о новом алгоритме для разреженных графов.
• Алгоритм даёт ускорение только при средней степени < 3, если граф не триллионных размеров.
• MarkusQ уточнил: при m < 3n это ≈ степень < 6, так что двумерные решётки всё ещё выигрывают.
• Вывод: улучшение полезно, но не универсально.