Представьте, что вам показывают ряд чисел: 1, 6, 21, 107 и — внимание! — 47 176 870. Кажется естественным спросить: какое число идёт дальше?
Угадать его невозможно. Эти значения — первые пять членов так называемой последовательности «занятого бобра». Она связана с одной из самых глубоких и трудных проблем теоретической информатики. Вычисление её членов оказывается настолько сложным, что уже более шестидесяти лет этой задачей занимаются и профессиональные математики, и энтузиасты.
Первые четыре числа были установлены ещё в 1960–1970-х годах. Пятое же, BB(5), оказалось во много раз больше предыдущих и лишь недавно — в прошлом году — было окончательно определено благодаря совместной работе группы любителей-исследователей в онлайн-сообществе Busy Beaver Challenge.
А вот значение шестого числа, BB(6), остаётся неизвестным. Известны лишь нижние границы, и они колоссальны. В 2022 году удалось доказать, что BB(6) настолько велико, что его невозможно даже записать привычным способом: если бы каждую цифру пытаться нанести на атом, атомы Вселенной закончились бы задолго до того, как удалось бы зафиксировать хоть сколько-нибудь значимую часть числа.
Учёный-информатик Скотт Ааронсон (Техасский университет в Остине) подчеркнул: это величина, которую мы не в силах ни вообразить, ни тем более «удержать в руках».
И всё же охотники за «бобрами» продолжают двигать границы. Недавно один из самых активных и загадочных участников конкурса сумел доказать новый, ещё более впечатляющий нижний предел для BB(6) — и менее чем через две недели снова превзошёл собственный рекорд. По сравнению с его результатами оценка 2022 года выглядит микроскопической.
Как заметил информатик Уильям Гасарч (Университет Мэриленда), шестое число буквально возносит нас в мир запредельных величин.
«Ловушка для бобра» связана с одной из самых известных и трудных проблем информатики: можно ли заранее определить, завершит ли программа работу или будет выполняться бесконечно?
Ещё в 1936 году Алан Тьюринг показал, что универсального метода для этого не существует. Это открытие получило название проблемы остановки. Суть в том, что любая процедура, которая сможет корректно решать задачу для одних программ, обязательно окажется бесполезной для других. Есть ситуации, в которых никакой алгоритм не сможет дать ответ.
Чтобы доказать это, Тьюринг ввёл строгую математическую модель вычислений — машину Тьюринга. В этой модели программы описываются как воображаемые устройства, выполняющие пошаговые действия по набору простых правил. Чем больше таких правил у машины, тем богаче её поведение и тем труднее заранее понять, завершится ли её работа или она зациклится навсегда.
А насколько всё усложняется? В 1962 году математик Тибор Радо предложил новый подход — он придумал игру под названием «занятый бобёр».
Правила такие: выбирается число n — это количество правил машины Тьюринга. Нужно найти такую машину с n правилами, которая сделает больше всех шагов, прежде чем остановится. Эта машина и называется «занятым бобром», а соответствующее число, BB(n), — это максимальное количество её шагов.
На первый взгляд задача кажется простой. Нужно лишь:
- Перечислить все возможные машины с n правилами.
- Смоделировать их работу на компьютере.
- Отсечь те, что сразу уходят в бесконечные циклы.
- Для остальных записать, сколько шагов они успели сделать.
Та машина, что проработает дольше всех, и будет «бобром-рекордсменом».
Но на практике всё гораздо сложнее. Количество возможных машин растёт лавинообразно с увеличением числа правил. Проверять каждую вручную бессмысленно, поэтому приходится писать специальные программы, чтобы классифицировать и отбраковывать варианты.
Некоторые машины легко раскусить: они быстро останавливаются или застревают в очевидных циклах. Но есть и такие, что работают очень долго, не проявляя никаких заметных закономерностей. И именно здесь в полную силу проявляется «проклятие проблемы остановки».
Чем больше правил у машины, тем больше вычислительной мощности требуется для анализа. Но простого увеличения мощности недостаточно — некоторые машины работают так долго, что их пошаговое моделирование становится просто невозможным. Чтобы разобраться с ними, нужны специальные математические трюки.
Как отметил инженер-программист и опытный исследователь «бобров» Шон Лигоцки, современные технологии, конечно, помогают, но их возможностей далеко не всегда хватает.
И всё же даже самые мощные компьютеры и самые хитрые алгоритмы оказываются бессильны перед некоторыми машинами Тьюринга. Они работают так долго и так непредсказуемо, что шаг за шагом моделировать их попросту невозможно. Для этого уже нужны не железо и код, а новые математические идеи. Именно здесь охота за «занятым бобром» превращается в настоящее приключение на грани науки и искусства — где числа перестают быть просто числами и становятся вызовом для нашего воображения.
Источник: https://t.me/mathematics_not_for_you.
Математика не для всех.
* * *
Мы привыкли считать, что «гугол» (10^100) - это много. Мы знаем, что количество атомов во всей наблюдаемой Вселенной огромно (примерно (10^80) ).
Но есть Число Грэма (G). И по сравнению с ним гугол - это даже не ноль. Это ничто.
Насколько оно большое?
Вы не можете записать Число Грэма. Даже если бы вы использовали каждый атом во Вселенной как чернила, и на каждом атоме написали бы по цифре... вам не хватило бы места. Вселенная слишком маленькая, чтобы просто записать это число, даже самым мелким шрифтом.
Обычная запись степеней (типа 10^50) здесь не работает - башни из степеней просто смешны для описания масштаба. Математикам пришлось изобрести специальную «стрелочную нотацию Кнута» (↑↑↑), чтобы хоть как-то его обозначить.
Почему оно может вас убить? Звучит как шутка, но есть физическое обоснование того, почему Число Грэма нельзя представить целиком.
Согласно современной физике, информация - это энергия, а энергия эквивалентна массе (E=mc^2). Чтобы запомнить информацию, нейроны вашего мозга должны изменить состояние. Если вы попытаетесь загрузить в голову все десятичные знаки Числа Грэма, плотность информации (энтропия) станет настолько высокой, что ваш мозг сколлапсирует под собственным весом. Буквально: Ваш череп превратится в маленькую черную дыру задолго до того, как вы запомните даже ничтожную долю этого числа.
Зачем оно вообще нужно?
Это не просто бред сумасшедшего ученого. Число Грэма появилось как верхняя граница решения серьезной задачи в Теории Рамсея (раздел математики, изучающий порядок в хаосе). Оно отвечает на вопрос о гиперкубах в многомерных пространствах. Ответ находится где-то между 6 и... Числом Грэма.
Итог: Математика - это единственная наука, где можно оперировать объектами, которые физически не могут существовать в нашей реальности, потому что они ее сломают.
Источник. @Pomatematike
Но есть Число Грэма (G). И по сравнению с ним гугол - это даже не ноль. Это ничто.
Насколько оно большое?
Вы не можете записать Число Грэма. Даже если бы вы использовали каждый атом во Вселенной как чернила, и на каждом атоме написали бы по цифре... вам не хватило бы места. Вселенная слишком маленькая, чтобы просто записать это число, даже самым мелким шрифтом.
Обычная запись степеней (типа 10^50) здесь не работает - башни из степеней просто смешны для описания масштаба. Математикам пришлось изобрести специальную «стрелочную нотацию Кнута» (↑↑↑), чтобы хоть как-то его обозначить.
Почему оно может вас убить? Звучит как шутка, но есть физическое обоснование того, почему Число Грэма нельзя представить целиком.
Согласно современной физике, информация - это энергия, а энергия эквивалентна массе (E=mc^2). Чтобы запомнить информацию, нейроны вашего мозга должны изменить состояние. Если вы попытаетесь загрузить в голову все десятичные знаки Числа Грэма, плотность информации (энтропия) станет настолько высокой, что ваш мозг сколлапсирует под собственным весом. Буквально: Ваш череп превратится в маленькую черную дыру задолго до того, как вы запомните даже ничтожную долю этого числа.
Зачем оно вообще нужно?
Это не просто бред сумасшедшего ученого. Число Грэма появилось как верхняя граница решения серьезной задачи в Теории Рамсея (раздел математики, изучающий порядок в хаосе). Оно отвечает на вопрос о гиперкубах в многомерных пространствах. Ответ находится где-то между 6 и... Числом Грэма.
Итог: Математика - это единственная наука, где можно оперировать объектами, которые физически не могут существовать в нашей реальности, потому что они ее сломают.
Источник. @Pomatematike
Комментариев нет:
Отправить комментарий