На базовом уровне двухмерные клеточные автоматы просты. Есть сетка, у сетки есть ячейки, у ячеек есть состояния. Со временем состояния отдельных клеток меняются. Вот и все.
К счастью, я не верю в простое изучение вещей на базовом уровне, потому что клеточные автоматы намного увлекательнее, чем просто сетки и ячейки. Хотя он уходит своими корнями в математические академические круги, теперь он повлиял на все, от компьютерных наук до философии.
Правила
Как было сказано выше, двухмерный клеточный автомат основан на сетке, в которой размещены ячейки. Эта сетка может быть любого размера, и для примера представьте, что это бесконечно большой лист графической бумаги. Каким бы крутым ни был этот очень-очень большой лист бумаги, чтобы все стало действительно интересным, нам нужно добавить к нему правила.
Допустим, для нашего набора правил наши ячейки могут иметь два состояния: «живые» (заполненные) и «мертвые» (пустые). Каждая ячейка также имеет соседей, и окружающие ячейки можно считать ее «соседями». Мы будем устанавливать наши правила на основе соседей каждой ячейки.
Двумя наиболее популярными районами, на которых основываются наши правила, являются район Мура, район и район фон Неймана (см. изображение). В моем примере я буду использовать район Мура.
Интересный факт: общее количество автоматов, возможных для нашей системы, можно рассчитать следующим образом:
(num_cells_in_neighborhood)
(num_states)^
(num_states)^
В нашем случае это 2^2^9, или: 1,34 * 10¹⁵⁴. Это огромное число! Огромные числа — это здорово! Клеточные автоматы — это круто!
Итак, давайте зададим нашим ячейкам некоторые правила, основанные на их соседстве. Набор правил для двумерного клеточного автомата с двумя состояниями можно упростить до (BX/SY). Числа, следующие за B и предшествующие «/», указывают точное количество соседей, необходимое для того, чтобы пустая ячейка была B орна. Числа, следующие за S, обозначают точное количество соседей, необходимых живой ячейке для выживания S. Таким образом, если бы у нас был набор правил (B3/S23), мертвая ячейка с ровно 3 соседями стала бы живой, а живая ячейка с 2 или 3 живыми соседями будет оставаться в живых, пока время (t) шагает вперед. Все остальные ячейки, те, у которых 1 или 0 соседей, или 4 или более соседей, умрут.
Игра жизни
Правила, которые мы только что создали, были впервые придуманы в 1970 году Джоном Конвеем. Получившуюся систему клеточных автоматов он назвал «Игрой жизни». Его аргументы в пользу правил были:
Любая живая клетка с менее чем двумя живыми соседями умирает, как если бы это было вызвано недостаточным населением.
Любая живая клетка с двумя-тремя живыми соседями живет до следующего поколения.
Любая живая клетка с более чем тремя живыми соседями умирает, как бы от перенаселения.
Любая мертвая клетка, имеющая ровно три живых соседа, становится живой клеткой, как бы путем размножения.
Эта «игра» является самой популярной и широко изученной системой клеточных автоматов, потому что закономерности развиваются сумасшедшим и захватывающим образом. Можно начать с простой начальной конфигурации со сроком службы, который может длиться тысячи поколений. Примером этого является «Желудь», конфигурация, состоящая всего из 7 начальных живых ячеек и требующая 5203 поколений для достижения стабильной конечной точки.
Обратите внимание, насколько больше и сложнее стабилизированная сетка по сравнению с исходной конфигурацией. Моделирование таких конфигураций, как Acorn и других, — это то, как Конвей назвал свой набор правил «Игрой жизни», поскольку он может имитировать подъем, падение и изменения общества «живых» организмов. На самом деле Life широко используется в исследованиях информатики, физики, биологии, биохимии, экономики, математики, философии и генеративных наук. Хотя философия может показаться неуместной, «Жизнь» использовалась для демонстрации того, что конструктивная организация и дизайн могут возникнуть без реального дизайнера. Философы, такие как Дэниел Деннет, использовали Жизнь, чтобы теоретизировать, как сложные конструкции в нашей собственной вселенной, такие как свобода воли и сознание, могут возникать из простого набора физических законов, точно так же, как законы внутри Жизни.
Хватит сводить меня с ума и покажи мне крутые штуки
Я пошел дальше и создал ОЧЕНЬ элементарный симулятор Game of Life и выложил его на свой гитхаб:
http://hdwatts.github.io/game_of_life/
Кнопки внизу могут отображать различные повторяющиеся шаблоны, которые могут возникать во время моделирования.
- Натюрморт: категория шаблонов, которые не меняются со временем и считаются стабильными.
- Осциллятор: категория паттернов, которые будут меняться со временем, но будут работать бесконечно в течение заданного периода времени. Они тоже считаются стабильными.
- Космические корабли: категория шаблонов, бесконечно движущихся в заданном направлении. К этой категории относится знаменитая формация планер. Космические корабли не считаются стабильными до тех пор, пока они не «сбежали» (не могут взаимодействовать с другим шаблоном).
Существуют и другие шаблоны. Помните Acorn? Желудь — это пример Мафусаила, которые представляют собой шаблоны, которые могут развиваться в течение многих поколений, прежде чем стабилизироваться.
Публикуя свою «игру» для всего мира, Джон Конвей бросил вызов своим читателям, что ни один шаблон не может развиваться бесконечно. В основном: никогда не будет исходной конфигурации, которая будет продолжать генерировать новые вечные клеточные структуры. С философской точки зрения этот вызов довольно антиутопичен, как будто эта «игра» имитирует то, как устроена жизнь в нашей вселенной, это говорит о том, что жизнь, какой мы ее знаем, не может расти бесконечно, и мы обречены либо стабилизироваться, либо уничтожить себя.
Он предложил невероятно щедрый приз в размере 50 долларов тому, кто сможет доказать его неправоту, и группа ученых из Массачусетского технологического института (которые отчаянно нуждались в деньгах) приняли вызов и создали планерную пушку. strong>, пример которого я включил в свой инструмент (примечание: это чертовски круто).
Продвинутое безумие
Охватив бесконечный рост, люди начали исследовать, что еще можно сделать с Жизнью. Исследователи создали более сумасшедшие пушки:
А затем создали «пуфферы» или узоры, которые движутся как космический корабль, оставляя за собой обломки:
Что еще более безумно, они создали «грабли», которые представляют собой шаблоны, которые, двигаясь как космический корабль, создают больше космических кораблей по мере их движения:
Однако одним из самых безумных и крутых паттернов, которые можно создать в игре «Жизнь», являются «заводчики», которые, двигаясь как космический корабль, генерируют пушки/грабли, которые генерируют космические корабли.
Уделите минутку, чтобы оценить, насколько великолепна эта анимация слева.
Эти удивительные планерные пушки, о которых говорилось ранее? Да, этот заводчик выплевывает их, двигаясь вправо. Мы перешли от «Невозможно создать паттерн, который бесконечно генерирует ячейки» к «Мы создали паттерн, который создает бесконечное количество паттернов, которые бесконечно генерируют клетки».
…и это еще не самое безумное
Далее следует, наверное, самая крутая вещь, которую можно создать в рамках этих правил:
«Глайдеры могут интересным образом взаимодействовать с другими объектами. Например, если два планера выстрелить в блок правильным образом, блок переместится ближе к источнику планеров. Если правильно выстрелить по трем глайдерам, блок отодвинется дальше. Эта «память скользящего блока» может использоваться для имитации счетчика. Можно построить логические элементы, такие как И, ИЛИ и НЕ, используя планеры. Можно построить шаблон, который действует как конечный автомат, подключенный к двум счетчикам. У него такая же вычислительная мощность, как у универсальной машины Тьюринга, поэтому теоретически Игра «Жизнь» не уступает любому компьютеру с неограниченной памятью и без ограничений по времени: она завершена по Тьюрингу».
Вы можете построить компьютер в игре жизни…
И если вы можете собрать компьютер….
Вы можете построить саму жизнь.
