Задача Busy Beaver Challenge, известная своей сложностью в теоретической информатике, теперь дает настолько большие ответы, что их невозможно записать с помощью стандартных математических обозначений.
Иллюстрация: Кристина Армитаж/Quanta MagazineСохранить эту историю Сохранить эту историю
Оригинальная версия этой истории была опубликована в журнале Quanta Magazine.
Представьте, что кто-то даёт вам список из пяти чисел: 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 года выглядеть просто ничтожной.
«Я не перестаю удивляться, — сказал Уильям Гасарч, специалист по информатике из Мэрилендского университета. — Шесть выводит нас в стратосферу больших чисел».
Бобровая ловушка
Самый сложный вопрос, стоящий за цифрами о занятости бобров, заключается в следующем: если известен код компьютерной программы, можно ли сказать, остановится ли она в конце концов или будет работать вечно?
В 1936 году пионер логики Алан Тьюринг доказал, что не существует универсальной процедуры для ответа на этот вопрос, который получил название «проблема остановки». Любой метод, работающий для одних программ, окажется неэффективным для других, а в некоторых случаях вообще не будет работать ни один метод.
Тьюринг доказал этот основополагающий результат, разработав формальную математическую модель вычислений, в которой программы представлены гипотетическими устройствами, ныне называемыми машинами Тьюринга. Каждая машина Тьюринга выполняет вычисления дискретными шагами в соответствии с уникальным списком простых правил. Чем больше правил у машины Тьюринга, тем сложнее становится её поведение и тем сложнее определить, остановится ли она.
Иллюстрация: Кристина Армитаж/Quanta MagazineНо насколько сложнее? В 1962 году математик Тибор Радо придумал новый способ исследовать этот вопрос с помощью игры, которую он назвал «занятой бобр». Чтобы начать игру, выберите определённое количество правил — назовём это число n. Ваша цель — найти машину Тьюринга с n правилами, которая работает дольше всего, прежде чем остановится. Эта машина называется «занятой бобр», а соответствующее число «занятой бобр» BB(n) — это количество шагов, которые она делает.
В принципе, если вы хотите найти «занятого бобра» для любого заданного n, вам нужно сделать всего несколько вещей. Во-первых, перечислите все возможные машины Тьюринга, работающие по правилу n. Затем смоделируйте работу каждой машины с помощью компьютерной программы. Обратите внимание на явные признаки того, что машины никогда не остановятся, например, многие машины попадут в бесконечные повторяющиеся циклы. Отбросьте все эти машины, которые не останавливаются. Наконец, запишите, сколько шагов каждая другая машина сделала до остановки. Машина с наибольшим временем работы и есть ваш «занятый бобр».
На практике это становится сложнее. Во-первых, количество возможных машин быстро растёт с каждым новым правилом. Анализировать их все по отдельности было бы безнадёжно, поэтому вам придётся написать специальную программу для классификации и отбраковки машин. Некоторые машины легко классифицировать: они либо быстро останавливаются, либо попадают в легко распознаваемые бесконечные циклы. Но другие работают долго, не проявляя никакой очевидной закономерности. Для таких машин проблема остановки заслуживает своей пугающей репутации.
Чем больше правил вы добавляете, тем больше вычислительной мощности вам требуется. Но простого перебора недостаточно. Некоторые машины работают так долго, прежде чем остановиться, что пошаговое моделирование их работы невозможно. Для измерения времени их работы требуются хитрые математические приёмы.
«Технологические усовершенствования, безусловно, помогают», — сказал Шон Лигоцки, инженер-программист и опытный охотник на бобров. «Но пока они помогают лишь до поры до времени».
Конец эпохи
Занятые охотники на бобров начали всерьез заниматься проблемой BB(6) в 1990-х и 2000-х годах, когда поиски BB(5) зашли в тупик. Среди них были Шон Лигоцки и его отец, Терри, прикладной математик, которые запускали свою поисковую программу в нерабочее время на мощных компьютерах Национальной лаборатории Лоуренса в Беркли. В 2007 году они создали машину Тьюринга с шестью правилами, которая побила рекорд по длительности работы: число шагов, которые она делала до остановки, составляло почти 3000 цифр. Это колоссальное число по любым обычным меркам. Но оно не слишком велико, чтобы его записать. При использовании шрифта 12 пунктов эти 3000 цифр едва ли займут один лист бумаги.
В 2022 году Шон Лигоцки открыл машину Тьюринга с шестью правилами, время работы которой содержит больше цифр, чем число атомов во Вселенной.
Фотография: Кира ТрейбергсТри года спустя словацкий студент бакалавриата по информатике Павел Кропиц решил заняться поиском BB(6) в рамках дипломной работы. Он написал собственную программу поиска и запустил её в фоновом режиме на сети из 30 компьютеров в университетской лаборатории. Через месяц он нашёл машину, которая работала гораздо дольше, чем та, что обнаружили Лигоцкие, — нового «чемпиона», как выражаются занятые охотники на бобров.
«Мне повезло, потому что в лаборатории уже жаловались на загрузку моего процессора, и мне пришлось немного сбавить обороты», — написал Кропиц в личном сообщении на Discord-сервере Busy Beaver Challenge. Спустя ещё месяц поисков он побил собственный рекорд, создав машину, время выполнения которой превысило 30 000 цифр — этого хватило бы примерно на 10 страниц.
Машина Кропица удерживала рекорд BB(6) 12 лет. Затем, в мае 2022 года, Шон Лигоцки устроился на новую работу, где у него был доступ к мощному компьютерному кластеру, и решил попробовать запустить свой старый код на более новом оборудовании. И действительно, он нашёл нового чемпиона, который побил рекорд Кропица. Это открытие вызвало бурную активность. Дважды в течение двух недель Лигоцки объявлял о новом рекорде в почтовой рассылке «Busy Beaver». Каждый раз Кропиц побивал его рекорд в течение трёх дней. Лигоцки вспоминает, как его отец восхищался тем, как Кропицу это удалось.
«Он шутил, что, по его мнению, Павел уже решил BB(6)», — сказал Лигоцкий. «Всякий раз, когда мы находим чемпиона, он просто достаёт из сумки тот, что побольше».
Однако последние две машины, обнаруженные Лигоцки и Кропицем, работали не просто дольше действующего чемпиона — их время работы было на совершенно новом уровне.
Чтобы разобраться с такими большими числами, нам нужно вернуться к привычной математике сложения и умножения. Начнём со сложения n копий числа — это и есть определение умножения на n. Если же вместо этого умножить n копий числа, это называется возведением в степень. Что же произойдёт, если многократно возводить число в степень? Этот процесс определяет новую операцию, называемую тетрацией, которая обозначается двумя стрелками, направленными вверх.
Тетрация быстро разрастается. 10↑↑1 — это всего лишь 10. Но 10↑↑2 — это 1010, или 10 миллиардов, а 10↑↑3 — это 10 в 10-миллиардной степени: единица и 10 миллиардов нулей. Чтобы записать все цифры, понадобится стопка бумаги высотой в тысячу футов. При 10↑↑4 вы пересекаете символический порог, где вопрос о наличии бумаги уже не стоит — цифр во Вселенной гораздо больше, чем атомов.
Иллюстрация: Сэмюэл Веласко/Quanta MagazineКогда Лигоцкий во второй раз побил рекорд Кропица, он использовал машину Тьюринга с шестью правилами, которая работала более 10↑↑5 шагов, прежде чем остановиться. Кропиц ответил машиной, которая работала 10↑↑15 шагов — это башня из десятков высотой в пятнадцать этажей. Они оставили привычный мир цифр далеко позади.
«Это был конец эпохи», — написал Кропиц в личном сообщении.
Это также стало концом целой эпохи в другом отношении. До этого игра «Занятые бобры» была соревнованием, и исследователи в основном работали в одиночку. Затем был создан проект «Занятые бобры», положивший начало новой эре сотрудничества.
Новый класс сумасшедших
Конкурс Busy Beaver Challenge был основан в 2022 году аспирантом факультета компьютерных наук Тристаном Стерином с единственной целью — строго доказать истинную ценность BB(5). Летом 2024 года группа добилась успеха благодаря ключевому вкладу таинственного новичка, известного только под псевдонимом mxdys.
Новость о результате появилась в Quanta, где её случайно увидела Кейтлин Дусетт, студентка бакалавриата по информатике из Политехнического университета Вирджинии. Вскоре она присоединилась к сообществу Busy Beaver Challenge, поначалу лишь изредка заглядывая на сервер Discord. Но в мае она сделала потрясающее открытие и с тех пор стала одним из самых активных участников поиска BB(6). «Меня это просто зацепило», — сказала она. «Это такой замечательный набор задач».
За год, прошедший с момента завершения доказательства BB(5), mxdys уверенно продвигался к решению задачи BB(6), используя сложные автоматизированные методы для классификации всех машин, за исключением нескольких тысяч «отстающих». Дусетт копалась в списке «отстающих», когда нашла одну, которая выглядела особенно многообещающей. Проведя более глубокий анализ с помощью Шона Лигоцки, она обнаружила, что её время работы уступало только времени работы действующего чемпиона Кропица. Более того, машина Дусетт принадлежала к классу машин, известных как счётчики сдвига и переполнения, которые достигают длительного времени работы, используя совершенно иной механизм, чем чемпион Кропица.
«Удивительно видеть, что эти трудолюбивые бобры нашли новую технологию», — сказал Лигоцкий.
Несколько других занятых охотников на бобров ранее обнаружили счетчики сдвига с переполнением, которые останавливались после долгого времени, но открытие Дусетта заставило команду заподозрить, что таких машин было больше, чем они предполагали. И если некоторые из первых изученных машин приблизились к рекорду Кропица, другие, вероятно, превзойдут его. Участники Busy Beaver Challenge бросились анализировать другие счетчики сдвига с переполнением, но mxdys опередил их. 16 июня они объявили об открытии нового чемпиона, который остановился после 10↑↑107 шагов — то есть его время работы равно башне из десятков высотой с 10 миллионов этажей. Записать это число в виде строки цифр не представляется возможным. Но даже запись его в виде башни степеней становится рискованной: шрифтом 12 пунктов эта строка из десятков растянется примерно на 25 миль.
Кропиц, увидевший эту новость во время отпуска, смирился с потерей титула, написав в Discord: «К сожалению, на этот раз я не смогу показать свой трёхдневный трюк». Утешительный приз ему очень помог. Месяцем ранее он установил рекорд по продолжительности работы машины Тьюринга с семью правилами. По крайней мере, пока Кропиц остаётся в таблице лидеров.
За пределами самого большого
Новый рекорд продержался недолго. Неделю спустя mxdys снова побил его, выпустив машину, время работы которой — в очередной раз — находится на качественно новом уровне. Чтобы записать это в наиболее краткой форме, нам нужно ввести абсурдную математическую операцию, называемую пентацией, представленную тремя стрелками, направленными вверх. Пентация — это повторяющаяся тетрация, то есть она имеет такое же отношение к тетрации, как тетрация к возведению в степень.
Общее количество шагов, которое новый чемпион mxdys сделал до остановки, превысило 2↑↑↑5, или 2↑↑(2↑↑(2↑↑(2↑↑2))). Чтобы расшифровать это выражение, нужно раскрыть скобки: 2↑↑2 равно 4, а 2↑↑4 — чуть больше 65 000. В итоге получается 2↑↑(2↑↑65 000), что делает высоту итоговой стопки двоек непостижимо большим числом. Забудьте о написании башни степеней, простирающейся на мили или мегапарсеки. Даже эта более компактная запись больше не вмещается во Вселенную.
Иллюстрация: Кристина Армитаж/Quanta MagazineЭтот новый результат пока лишь указывает на нижний предел BB(6) — истинное значение может быть ещё выше. Занятые охотники на бобров не рассчитывают получить окончательный ответ в ближайшее время. Первым признаком проблем стала гигантская машина Тьюринга с шестью правилами, которую команда назвала Антигидрой и которую mxdys обнаружил в прошлом году.
Антигидра почти наверняка никогда не останавливается. Но исследователям не удалось это доказать. И тому есть веская причина: охотница на бобров по имени Рашелин, работающая на износ, показала, что вопрос об остановке Антигидры тесно связан с известной нерешённой математической проблемой, известной как гипотеза Коллатца. С тех пор команда обнаружила множество других шестиправильных машин с похожими характеристиками. Уничтожение Антигидры и её сородичей потребует концептуальных прорывов в чистой математике.
Но для заядлых охотников на бобров это не повод отчаиваться. Ещё есть тысячи машин Тьюринга с шестью правилами, которые стоит изучить, и каждая из них обладает своим богатым набором функций.
«Для меня самая веская причина заниматься математикой — это развлечение. Это искусство», — написала Рэйчелин в личном сообщении в Discord. «Всегда найдётся что-то новое».
Оригинальная статья перепечатана с разрешения журнала Quanta Magazine, редакционно-независимого издания Фонда Саймонса, миссия которого заключается в повышении уровня понимания науки среди общественности путем освещения научных разработок и тенденций в области математики, физических и биологических наук.
Источник: www.wired.com
