Подписывайтесь на канал в Яндекс. Дзен или на канал в телеграм "Математика не для всех", чтобы не пропустить интересующие Вас материалы. Также есть группы в VK, Одноклассниках и Facebook : всё для математического просвещения!
Приветствую Вас, уважаемые Читатели! В прошлом месяце я рассказывал про число Грэма - невероятно огромное число, которое, в своё время, задавало верхнюю планку в мире больших чисел. Однако, со временем математики придумали еще более причудливые конструкции, которые несоизмеримо больше даже чудовищного числа Грэма.
Об одном из таких чисел мы и поговорим сегодня. В английском варианте, это число появляется в результате решения задачи "busy beaver" - дословно "усердных бобров". Узнаем же подробнее, о чём идет речь. Поехали!
Суть задачи
Пусть дана лента с бесконечным числом клеточек и бобер, который находится на одной из них. Бобер может красить клетку, на которой он находится и перемещаться влево или вправо, руководствуясь некоторым количеством команд.
Решение задачи состоит в том, чтобы дать бобру последовательность команд, которые он должен выполнять, чтобы в результате быть "вечно занятым", т.е., иначе говоря, написать такую программу действий бобра, которая зациклится.
Одна команда состоит в том, чтобы посмотреть какие клеточки окружают бобра, в зависимости от этого покрасить клеточку, где он стоит либо в белый, либо в черный цвет, а затем пойти вправо или влево. Пример команды:
Если дать бобру одну такую команду, то бобер начнет покраску и уйдет в бесконечность влево, т.е. не будет зациклен. Однако, если дать еще команду, например проверять, есть ли справа черная клетка и тогда закрашивать ту, на которой находится и идти вправо. можно достичь цикличности.
В данном случае до зацикливания бобер может покрасить максимум 4 клеточки при наличии 2 команд. Такое число обозначается BB(2) = 4.
Функция усердного бобра - невычислимая. Не существует алгоритма, чтобы рассчитать ее значение для определенного n. Чтобы узнать её значение необходимо только полностью перебирать все возможные варианты, что требует нереальных вычислительных мощностей
Самое интересное в том, что хоть BB(n) начинается с маленьких чисел, оно начинает невообразимо расти почти сразу. Если BB(3) = 6, BB(4) = 13, то для 5 команд современные компьютеры уже не способны выдать решение.
Число BB(10) уже невообразимо больше числа Грэма и даже больше еще одного гиганта TREE(3), о котором я расскажу в следующих материалах.
Ставьте лайк и подписывайтесь! ! ССЫЛКА НА ДЗЕН-КАНАЛ и TELEGRAM.
Второй проект - канал "Русский язык не для всех".
