Why Busy Beaver hunters fear the Antihydra
Онлайн-сообщество недавно определило BB(5) = 47,176,870, первый большой прорыв в проблеме "busy beaver game" за 50 лет. Следующая цель - BB(6), но исследователи не ожидают её достижения в ближайшее время из-за программы Antihydra, которая напоминает нерешенную математическую проблему Collatz conjecture.
Busy beaver numbers измеряют сложность вычислений, которые могут выполнить простые компьютерные программы. В этих исследованиях программы представлены машинами Тьюринга - гипотетическими устройствами, считывающими и записывающими 0 и 1 на бесконечной ленте. Каждая машина имеет уникальный набор правил, определяющих её поведение.
Antihydra представляет особую сложность, так как её поведение тесно связано с проблемой Collatz conjecture, одной из самых известных нерешенных задач в математике. Эта связь делает BB(6) практически недостижимым для точного определения в обозримом будущем.