Представьте, что кто-то даёт вам список из пяти чисел: 1, 6, 21, 107 и внезапно — 47 176 870. Догадаетесь, что будет дальше? 

Если вы не угадаете, ничего страшного — практически никто не угадывает. Вот первые пять чисел «усердного бобра» — последовательности, тесно связанной с одним из самых известных и сложных вопросов теоретической информатики. Он звучит так: сколько времени может работать машина Тьюринга с некоторым набором правил, пока не остановится. Определение значений чисел «усердного бобра» — сложнейшая задача, которая уже более 60 лет привлекает поклонников как среди профессиональных математиков, так и среди любителей. 

Исследователи определили первые четыре числа «усердного бобра» в 1960-х и 1970-х годах. Пятое число, BB(5), оказалось настолько большим, что установить его удалось только в прошлом году. Это выполнила команда, состоящая в основном из математиков-любителей, которые работают в онлайн-сообществе под названием Busy Beaver Challenge. 

Никто не знает, насколько велико число BB(6). У нас есть лишь нижние пределы — поистине ошеломляющие. В 2022 году охотники на усердных бобров установили, что BB(6) должно быть, как минимум, настолько велико, что его буквально невозможно записать в обычной десятичной системе счисления. Даже если бы вы наносили по одной цифре на каждый атом во Вселенной, атомов всё равно не хватило бы. 

Исследователи подчёркивают гигантские, ни с чем не сравнимые масштабы этого числа. «Это превосходит всё, что мы когда-либо могли бы постичь или к чему могли бы прикоснуться», — сказал Скотт Ааронсон, специалист по информатике из Техасского университета в Остине. 

Охотники на бобров теперь обнаружили, что это ошеломляюще большое число должно быть ещё больше. Открытие сделал один из самых загадочных и плодовитых участников проекта Busy Beaver Challenge. В июне он установил новый нижний предел для BB(6) и всего через девять дней снова побил рекорд. Новые результаты заставляют нижнюю границу из 2022 года выглядеть просто ничтожной. 

«Я не перестаю удивляться, — сказал Уильям Гасарч, специалист по информатике из Мэрилендского университета. — BB(6) выводит нас в стратосферу больших чисел». 

Бобровая ловушка

Главный вопрос чисел усердных бобров заключается в следующем: если известен код компьютерной программы, можно ли сказать, остановится ли она в конце концов или будет работать вечно? 

В 1936 году пионер логики Алан Тьюринг доказал, что не существует универсальной процедуры для ответа на этот вопрос, который получил название «проблема остановки». Любой метод, работающий для одних программ, окажется неэффективным для других, а в некоторых случаях вообще не будет работать ни один метод. 

Тьюринг доказал этот основополагающий результат, разработав формальную математическую модель вычислений, в которой программы представлены гипотетическими устройствами, ныне называемыми машинами Тьюринга. Каждая машина Тьюринга выполняет вычисления дискретными шагами в соответствии с уникальным списком простых правил. Чем больше правил у машины Тьюринга, тем сложнее становится её поведение и тем сложнее определить, остановится ли она. 

Но насколько сложнее? В 1962 году математик Тибор Радо придумал новый способ исследовать этот вопрос с помощью игры, которую он назвал «усердный бобр» (оригинальная публик��ция) . Чтобы начать, выберите определённое количество правил — назовём это число n. Смысл игры — среди всех машин Тьюринга с n правилами найти ту, которая работает дольше всех и всё-таки останавливается. Такая машина называется «усердный бобр», а соответствующее число усердного бобра BB(n) — это количество шагов, которые она делает. 

В принципе, если вы хотите найти «усердного бобра» для любого заданного n, вам нужно сделать всего несколько вещей. Во-первых, перечислите все возможные машины Тьюринга, работающие по правилу n. Затем смоделируйте работу каждой машины с помощью компьютерной программы. Обратите внимание на явные признаки того, что машины никогда не остановятся — например, многие машины попадут в бесконечные повторяющиеся циклы. Отбросьте все эти машины, которые не останавливаются. Наконец, запишите, сколько шагов каждая оставшаяся машина сделала до остановки. Машина с самым большим временем работы и есть ваш «усердный бобр». 

Но на практике это намного сложнее. Во-первых, количество возможных машин быстро растёт с каждым новым правилом. Анализировать их все по отдельности было бы безнадёжно, поэтому вам придётся написать специальную программу для классификации и отбраковки машин. Некоторые машины легко классифицировать: они либо быстро останавливаются, либо попадают в легко распознаваемые бесконечные циклы. Но другие работают долго, не проявляя никакой очевидной закономерности. Для таких машин проблема остановки заслуживает своей пугающей репутации. 

Чем больше правил вы добавляете, тем больше вычислительной мощности вам требуется. Но простого перебора недостаточно. Некоторые машины работают так долго, прежде чем остановиться, что пошаговая эмуляция их работы невозможна. Для измерения времени их работы требуются хитрые математические приёмы. 

«Технологические усовершенствования, безусловно, помогают», — сказал Шон Лигоцки, инженер по разработке программ и опытный охотник на усердных бобров. «Но пока они помогают лишь до поры до времени». 

Конец эпохи

Охотники на усердных бобров начали всерьёз заниматься проблемой BB(6) в 1990-х и 2000-х годах, когда поиски BB(5) зашли в тупик. Среди них были Шон Лигоцки и его отец, Терри, прикладной математик. Они запускали свою поисковую программу в нерабочее время на мощных компьютерах Национальной лаборатории Лоуренса в Бёркли. В 2007 году они нашли машину Тьюринга с шестью правилами, которая побила рекорд по длительности работы: количество шагов, которые она делала до остановки, состояло из почти 3000 цифр. Это по научным меркам огромное число, но его всё ещё можно записать. При использовании шрифта 12 пунктов эти 3000 цифр едва ли займут один лист бумаги.

Три года спустя словацкий студент по информатике Павел Кропиц решил заняться поиском BB(6) в качестве дипломной работы. Он написал собственную программу поиска и запустил её в фоновом режиме в сети из 30 компьютеров в университетской лаборатории. Через месяц он нашёл машину, которая работала гораздо дольше, чем та, что обнаружили Лигоцки. Охотники на усердных бобров называют такую машину «чемпионом». 

«Мне повезло, потому что в лаборатории уже жаловались на загрузку компьютеров, и мне пришлось немного сбавить обороты», — написал Кропиц в личном сообщении на Discord сервере Busy Beaver Challenge. Спустя ещё месяц поисков он побил собственный рекорд, создав машину, время выполнения которой превышало 30 000 цифр — этого хватило бы, чтобы заполнить около 10 страниц. 

Машина Кропица удерживала рекорд BB(6) 12 лет. Затем, в мае 2022 года, Шон Лигоцки устроился на новую работу, где у него был доступ к мощному компьютерному кластеру. Он решил попробовать запустить свой старый код на более новом оборудовании. И, конечно же, нашёл нового чемпиона, который побил рекорд Кропица. Это открытие вызвало бурную активность. Дважды в течение двух недель Лигоцки объявлял о новом чемпионе в почтовой рассылке «усердных бобров». Каждый раз Кропиц побивал его рекорд в течение трёх дней. Лигоцки вспоминает, что его отец восхищался тем, как Кропицу это удалось. 

«Он шутил, что, по его мнению, Павел уже решил BB(6)», — сказал Лигоцки. «Всякий раз, когда мы находим чемпиона, он просто достаёт из своей сумки новое число, которое немного больше». 

Однако последние две машины, обнаруженные Лигоцки и Кропицем, работали не просто дольше действующего чемпиона — их время работы было на совершенно новом уровне. 

Чтобы понять такие большие числа, нам нужно вернуться к привычной математике сложения и умножения. Начнём со сложения n копий числа — это и есть определение умножения на n. Если же вместо этого умножить n копий числа, мы получим возведение в степень. Что же произойдёт, если многократно возводить число в степень? Этот процесс определяет новую операцию, называемую тетрацией, которая обозначается двумя стрелками, направленными вверх. 

Тетрация быстро увеличивается. 10↑↑1 — это всего лишь 10. Но 10↑↑2 — это 10¹⁰, или 10 миллиардов, а 10↑↑3 — это 10 в 10-миллиардной степени: единица с 10 миллиардами нулей. Чтобы записать все цифры, понадобится стопка бумаги высотой в тысячу футов. При 10↑↑4 вы пересекаете символический порог, где вопрос о наличии достаточного количества бумаги уже не стоит — цифр во Вселенной гораздо больше, чем атомов.

Когда Лигоцки во второй раз побил рекорд Кропица, он использовал машину Тьюринга с шестью правилами, которая работала более 10↑↑5 шагов, прежде чем остановиться. Кропиц ответил машиной, которая работала 10↑↑15 шагов — это башня из десяток высотой в пятнадцать этажей. Они оставили привычный мир цифр далеко позади. 

«Это был конец эпохи», — написал Кропиц в личном сообщении. 

Это также стало концом эпохи в другом отношении. До этого игра «усердный бобр» была соревнованием, и исследователи в основном работали в одиночку. Затем был создан проект «Усердные бобры», положивший начало новой эре сотрудничества. 

Безумное число

Конкурс Busy Beaver Challenge был основан в 2022 году аспирантом по информатике Тристаном Стерином с единственной целью — строго доказать истинное значение BB(5). Летом 2024 года группа добилась успеха благодаря ключевому вкладу таинственного новичка, известного только под псевдонимом mxdys. 

Новость о результате появилась в Quanta Magazine, где её случайно увидела Кейтлин Дусетт, студентка информатики из Политехнического университета Вирджинии. Вскоре она присоединилась к сообществу Busy Beaver Challenge и поначалу лишь изредка заглядывала на сервер Discord. Но в мае она сделала потрясающее открытие и с тех пор стала одним из самых активных участников поиска BB(6). «Меня это просто зацепило», — сказала она. «Это очень красивый набор задач». 

За год, прошедший с момента завершения доказательства BB(5), mxdys уверенно продвигался к решению задачи BB(6), используя сложные автоматизированные методы для классификации всех машин, за исключением нескольких тысяч «отстающих». Дусетт копалась в списке «отстающих», когда нашла одну, которая выглядела особенно многообещающей. Проанализировав её более подробно с помощью Шона Лигоцки, она обнаружила, что её время работы уступало только времени работы действующего чемпиона Кропица. Более того, машина Дусетт принадлежала к классу машин, известных как счётчики сдвига и переполнения, которые достигают длительного времени работы, используя совершенно иной механизм, чем чемпион Кропица. 

«Волнующе видеть, что эти усердные бобры нашли новую технологию», — сказал Лигоцки. 

Несколько других охотников на усердных бобров ранее обнаружили счётчики сдвига с переполнением, которые останавливались после долгого времени. Но открытие Дусетт заставило команду заподозрить, что таких машин было больше, чем они предполагали. И если некоторые из первых изученных машин приблизились к рекорду Кропица, другие, вероятно, превзойдут его. Участники Busy Beaver Challenge бросились анализировать другие счётчики сдвига с переполнением, но mxdys опередил их. 16 июня они объявили об открытии нового чемпиона, который остановился после 10↑↑10⁷ шагов — то есть его время работы представляет собой башню из десяток высотой в 10 миллионов этажей. Записать это число в виде строки цифр не представляется возможным. Но даже запись его в виде башни степеней становится рискованной: записанная шрифтом 12 пунктов эта строка из десяток растянется примерно на 25 миль. 

Кропиц, увидевший эту новость во время отпуска, смирился с потерей титула, написав в Discord: «К сожалению, на этот раз я не смогу показать свой трёхдневный трюк». Утешительный приз ему очень помог. Месяцем ранее он установил рекорд по самой продолжительной работе машины Тьюринга с семью правилами. По крайней мере, пока Кропиц остаётся в таблице лидеров. 

За гранью возможного

Новый рекорд продержался недолго. Неделю спустя mxdys снова побил его, обнаружив машину, время работы которой — в очередной раз — находится на качественно новом уровне. Чтобы записать это в наиболее краткой форме, нам нужно ввести новую математическую операцию, называемую пентацией. Её обозначают уже тремя стрелками, направленными вверх. Пентация — это повторная тетрация, то есть она имеет такое же отношение к тетрации, как тетрация к возведению в степень. 

Общее количество шагов, которое новый чемпион mxdys сделал до остановки, превысило 2↑↑↑5, или 2↑↑(2↑↑(2↑↑(2↑↑2))). Чтобы расшифровать это выражение, нужно раскрыть скобки: 2↑↑2 равно 4, а 2↑↑4 — чуть больше 65 000. В итоге получается 2↑↑(2↑↑65 000), что делает высоту итоговой стопки двоек непостижимо большим числом. Забудьте о написании башни степеней, простирающейся на мили или мегапарсеки. Даже эта более компактная запись больше не помещается во Вселенную. 

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

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

Но для заядлых охотников на бобров это не повод отчаиваться. Ещё есть тысячи машин Тьюринга с шестью правилами, каждая из которых обладает своим уникальным поведением. 

«Для меня самая веская причина заниматься математикой — потому, что это весело. Это искусство», — написала Рэйчелин в личном сообщении в Discord. «Всегда найдётся что-то новое».

Автор перевода @arielf

НЛО прилетело и оставило здесь промокод для чита��елей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.