Математики нашли десятое дедекиндово число после 32 лет поисков
После трёх десятилетий поисков и не без помощи суперкомпьютера математики наконец обнаружили новый экземпляр особой последовательности целых чисел, названных в честь немецкого математика Дедекинда.
Только десятое в своём роде число, D (9) (первое будет D (0)), равно 286 386 577 668 298 411 128 469 151 667 598 498 812 366. Этот 42-значный монстр следует за 23-значным D (8), открытым аж в 1991 году.
Смысл дедекиндовых чисел сложно понять нематематику, не говоря уже о том, чтобы его вычислить. На самом деле, вычисления настолько сложны и включают в себя такие огромные числа, что не было уверенности в том, что D (9) когда-либо вообще найдут.
«В течение 32 лет вычисление D (9) было открытой задачей, и было сомнительно, что это число вообще когда-нибудь удастся вычислить», — говорит специалист по информатике Леннарт Ван Хиртум из Университета Падерборна в Германии.
В основе дедекиндовых чисел находятся булевы функции, или разновидность логики, которая выдаёт определённый результат на основе входных данных, состоящих всего из двух состояний, таких как истина и ложь, или 0 и 1.
Монотонные булевы функции — это функции, которые ограничивают логику таким образом, что замена 0 на 1 на входе приводит только к изменению выхода с 0 на 1, но не с 1 на 0.
Исследователи описывают это с помощью красного и белого цветов, а не 1 и 0, но идея та же.
Представление разрезов, образующих числа Дедекинда для размерностей 0, 1, 2 и 3.
«В принципе, монотонную булеву функцию в двух, трёх и бесконечном числе измерений можно представить как игру с n-мерным кубиком, — говорит Ван Хиртум. — Вы балансируете куб на одном углу, а затем окрашиваете каждый из оставшихся углов в белый или красный цвет».
«Есть только одно правило: вы никогда не должны располагать белый угол над красным. Это создаёт своего рода вертикальный красно-белый перекрёсток. Цель игры — подсчитать, сколько различных разрезов существует».
Первые несколько оказались довольно простыми. Математики подсчиттали, что D (0) равняется 2, затем идут 3, 6, 20, 168, 7581, 7828354, 2414682040998…
В 1991 году суперкомпьютеру Cray-2 (одному из самых мощных суперкомпьютеров того времени) и математику Дагу Видеманну потребовалось 200 часов, чтобы вычислить D (9) = 56130437228687557907788.
В итоге D (10) оказалась почти в два раза длиннее D (9), и для его расчёта потребовался особый вид суперкомпьютера: тот, который использует специализированные устройства под названием Field Programmable Gate Arrays (FPGA), способные параллельно выполнять несколько вычислений. Команда воспользовалась суперкомпьютером Noctua 2 в Университете Падерборна.
«Решение сложных комбинаторных задач с помощью FPGA — перспективная область применения, а Noctua 2 — один из немногих суперкомпьютеров в мире, с которым эксперимент вообще осуществим», — говорит компьютерный учёный Кристиан Плессл, руководитель Падерборнского центра параллельных вычислений (PC2), где хранится Noctua 2.
Чтобы Noctua 2 было с чем работать, потребовалась дальнейшая оптимизация. Используя симметрии в формуле для повышения эффективности процесса, исследователи дали суперкомпьютеру одну огромную сумму для вычисления — сумму, включающую 5,5×1018 членов — это чуть меньше, чем примерное количество песчинок на Земле.
Через пять месяцев Noctua 2 пришёл к ответу. Исследователи пока не упоминают о D (11), но мы можем предположить, что на его поиски уйдёт ещё как минимум 32 года.
