Фрактал песочной кучи
Насыпайте песчинки на одну клетку сетки. Как только в клетке оказывается четыре песчинки, она обрушивается: отдаёт по одной песчинке каждому из четырёх соседей, которые затем тоже могут обрушиться. Это продолжается, пока в каждой клетке не останется не больше трёх песчинок, — и куча песка оказывается вовсе не кучей, а замысловатым фракталом с симметрией восьмого порядка. Наблюдайте за этим в реальном времени при числе песчинок до 1 048 576, попробуйте другие решётки и посмотрите на лавины, которые прославили песочную кучу Бака, Тана и Визенфельда. Режим «Куча» кладёт введённое число песчинок на одну клетку и в реальном времени показывает их обрушения: клетка, в которой столько песчинок, сколько у неё соседей, отдаёт каждому из них по одной. Введите до 1 048 576 песчинок (можно и 2^20) или выберите пример; полоса показывает, насколько продвинулись обрушения, а миллион песчинок на квадратной решётке обрабатывается примерно полминуты. «Решётка» и «Начальная высота» меняют узор. Режим «Нейтральный» вычисляет нейтральный элемент группы песочной кучи для сетки n × n. Режим «Лавины» бросает песчинки по одной на сетку, с краёв которой они теряются; щёлкните по сетке или удерживайте на ней нажатие, чтобы сыпать песчинки в одно место, а график подсчитывает лавины по размеру. Прокручивайте колесо или сводите и разводите пальцы, чтобы менять масштаб, перетаскивайте, чтобы двигать, и дважды щёлкните, чтобы показать всю кучу; при увеличении каждая клетка показывает своё число. Уменьшите «Скорость», чтобы следить за обрушениями шаг за шагом.
Как это работает
- Введите число песчинок, до 1 048 576, или выберите пример, например 2^18 = 262 144, и смотрите, как куча обрушивается от центра наружу.
- Смените решётку на квадратную с диагоналями или треугольную либо начните со слоя в 1 или 2 песчинки на клетку и сравните узоры.
- Переключитесь в режим «Нейтральный» или «Лавины», увеличьте масштаб, пока каждая клетка не покажет своё число, и сохраните изображение.
Как обрушивается песочная куча
В каждой клетке сетки лежит какое-то число песчинок. Клетка, в которой столько песчинок, сколько у неё соседей (на квадратной сетке — четыре), неустойчива: она обрушивается и передаёт по одной песчинке каждому соседу. Теперь уже соседи могут стать неустойчивыми, так что одно обрушение способно вызвать целую лавину. Правило применяется, пока ни одна клетка не может обрушиться. Если начать с 1 024 песчинок на одной клетке, понадобится 20 384 обрушения, и останется куча шириной 25 клеток; 262 144 песчинки требуют более 1,2 миллиарда обрушений и расходятся на 375 клеток; а 1 048 576 песчинок — максимум, который допускает приложение, — требуют около 19,1 миллиарда обрушений и дают кучу поперечником 747 клеток. Вчетверо больше песчинок — куча вдвое шире.
Почему порядок не важен
Когда неустойчивы сразу несколько клеток, неважно, какая из них обрушится первой. Дипак Дхар показал в 1990 году, что итоговая устойчивая куча и даже число обрушений каждой клетки всегда одни и те же: песочная куча абелева, как сложение. Приложение пользуется этой свободой дважды. Оно позволяет клетке с большим числом песчинок раздать их за один раз, а не по четыре, и, поскольку куча на одной клетке так же симметрична, как её решётка, вычисляет только один сектор — восьмую часть квадратной решётки или двенадцатую часть треугольной — и зеркально отражает остальное.
Фрактал, который помнит свою решётку
Устойчивая куча далеко не случайна. Области с правильным узором из единиц, двоек и троек окаймлены тонкими линиями и заполнены уменьшенными копиями самих себя. Уэсли Пегден и Чарльз Смарт доказали в 2013 году, что с ростом кучи узор стремится к определённому пределу, а вместе с Лайонелом Левином показали, что правильные области связаны с аполлониевыми упаковками кругов. Форма помнит и свою сетку: на квадратной решётке с диагоналями или на треугольной решётке то же правило рисует другой фрактал с другой симметрией.
Лавины и самоорганизованная критичность
Пер Бак, Чао Тан и Курт Визенфельд придумали песочную кучу в 1987 году, чтобы объяснить, как природа может сама настраиваться на критическую точку. Если бросать песчинки наугад на сетку, края которой их теряют, то через некоторое время сетка приходит в стационарное состояние: большинство песчинок ничего не вызывают, немногие запускают лавину, проходящую через всю сетку, а промежуточные размеры подчиняются степенному закону — на графике в двойном логарифмическом масштабе это прямая линия. В режиме «Лавины» можно наблюдать, как формируется это состояние, сыпать песчинки в одно место и смотреть, как средняя высота приближается к 17/8 = 2,125 — значению, доказанному для бесконечной квадратной сетки.
Часто задаваемые вопросы
Что такое абелева модель песочной кучи?
Это клеточный автомат, предложенный Пером Баком, Чао Таном и Куртом Визенфельдом в 1987 году. В каждой клетке сетки лежат песчинки; клетка, в которой песчинок не меньше, чем соседей, обрушивается и отдаёт по одной песчинке каждому соседу. Модель называют абелевой, потому что порядок обрушений не меняет итогового результата; это свойство доказал Дипак Дхар в 1990 году.
Почему куча песка образует фрактал?
Обрушения разносят песчинки волнами, которые интерферируют друг с другом, и клетки укладываются в области с правильным узором из единиц, двоек и троек, разделённые тонкими линиями. Между крупными областями появляются их уменьшенные копии — на каждом масштабе, который допускает сетка. Узор детерминирован: одно и то же число песчинок всегда даёт в точности одну и ту же картину.
Сколько времени занимает миллион песчинок?
В приложении 1 048 576 песчинок на квадратной решётке обрабатываются на быстром компьютере примерно полминуты — это более 19 миллиардов обрушений, — а индикатор хода показывает, сколько уже сделано. Треугольная решётка и решётка с диагоналями обрабатываются быстрее, а кучи поменьше готовы почти сразу. Уменьшите «Скорость», чтобы наблюдать обрушения медленно.
Что такое нейтральный элемент группы песочной кучи?
Устойчивые кучи, к которым на конечной сетке можно возвращаться снова и снова, образуют группу, где сложение означает ссыпать две кучи вместе и дать им обрушиться. Её нейтральный элемент — это куча, которая при прибавлении ничего не меняет. На сетке n × n его можно найти, стабилизировав по 6 песчинок в каждой клетке, вычтя результат из 6 и снова стабилизировав, и выглядит он как самостоятельный фрактал.
Почему начальная высота может быть только 0, 1 или 2?
На квадратной решётке, где в каждой клетке уже лежат 3 песчинки, одна лишняя песчинка вызывает обрушения, которые никогда не прекращаются: лавина растёт бесконечно. Если в каждой клетке не больше 2 песчинок, любая куча стабилизируется, как доказали Энн Фей, Лайонел Левин и Юваль Перес, но чем выше начальный слой, тем больше и медленнее куча.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор