👾!
Возвращаемся к нашей экскурсии по модификациям клеточных автоматов. Объект сегодняшнего внимания – дефицитные правила (deficient rules). Это ещё более свежая вариация, чем рассмотренный в прошлом посте BSFKL, и была описана 5 лет назад энтузиастом 83bismuth38.
Модификация предполагает, что при рождении клетки на окружающих соседей налагается ограничение на рождение по этому переходу, согласно нотации Хенселя. Освежить в памяти, что из себя представляют переходы можно здесь.Читать полностью »
👾!
В прошлой статье о циклических КА мы мельком затронули тему альтернативных окрестностей, рассмотрев несколько примеров. Несмотря на то, что ранее мы использовали только окрестности Мура и фон Неймана, существует ещё множество прочих именованных окрестностей, а потенциал для создания новых ограничен лишь нашей фантазией.
Сегодняшний обзор мы совместим с ещё одним расширением: в статье об LtL было упомянуто, что параметры рождения и выживания клетки могут поддерживать множество значений и диапазонов в некоторых прочих конфигурациях. В первую очередь речь шла о HROT (Higher-Range Outer-Totalistic) – обобщении LtL конфигурации, на котором и будут наши сегодняшние примеры.
Читать полностью »
Всем привет! На написание этой статьи меня вдохновил автор YouTube канала PeaAshMeter. В своем видео автор показывает простейший генератор 2D мира, который основан на простейшем правиле клеточного автомата. Что такое клеточный автомат? Какие клеточные автоматы бывают? На эти и многие другие вопросы я попробую ответить.
Проект я решил написать на Python, но поскольку не являюсь экспертом в этой области, то любые замечания, предложения по улучшению кода или проекта — приветствуются!
В мире существует около 14 000 видов муравьёв, каждый из которых имеет собственное название. Но, даже если вы зададитесь такой целью, вы не найдёте ни в одном биологическом справочнике муравья Лэнгтона. Дело в том, что этот муравей — математическая абстракция, модель для описания поведения динамической системы. Иногда кажется, что математики вообще неравнодушны к муравьям — вспомним хотя бы уже ставший классическим муравьиный алгоритм. Да и во всяких логических моделях и задачах муравьи встречаются довольно часто.
Полагаю, всем программистам хорошо известен клеточный автомат жизнь (или эволюция), придуманный английским математиком Джоном Конвеем в 1970 году. Возможно, некоторые даже корпели над самописной программой, моделирующей клеточный автомат Конвея.Читать полностью »
Начнем разговор о мозге с несколько отвлеченной темы. Поговорим о клеточных автоматах. Клеточный автомат – это дискретная модель, которая описывает регулярную решетку ячеек, возможные состояния ячеек и правила изменений этих состояний. Каждая из ячеек может принимать конечное множество состояний, например, 0 и 1. Для каждой из ячеек определяется окрестность, задающая ее соседей. Состояние соседей и собственное состояние ячейки определяют ее следующее состояние.
Наиболее известный клеточный автомат – это игра «Жизнь». Поле в игре «Жизнь» состоит из ячеек. Каждая ячейка имеет восемь соседей. Задается начальная комбинация. Затем начинается смена поколений. Если у занятой ячейки два или три занятых (живых) соседа, то ячейка продолжает жить. Если соседей меньше 2 или больше 3, то ячейка умирает. Когда у пустой ячейки оказывается ровно 3 соседа в ней зарождается жизнь. Задав произвольную начальную комбинацию можно пронаблюдать ее эволюцию.
Читать полностью »
Этот мир просто охренеть какой сложный, каждый день поражаюсь.
Чтобы хоть как-то его познавать и при этом не съехать с катушек, нам, людишкам, с нашими жалкими мозгами приходится задумчиво смотреть на происходящее, анализировать увиденное и строить модели — абстракции, с помощью которых мы с некоторой точностью кое-что иногда можем предсказывать и даже наивно полагать, что понимаем, что же на самом деле происходит.
И знаете, что удивительно? Этот подход замечательно работает. Ну, почти всегда. По крайней мере, ничего лучше мы до сих пор не придумали.
Но вообще-то я не об этом. Я хочу рассказать об одной чрезвычайно интересной как с эстетической, так и с математической точки зрения категории этих самых моделей.
Да, я о клеточных автоматах, а именно — об их подмножестве, простейших клеточных автоматах (Elementary cellular automaton). В этой статье я поведаю, что это такое, какие они бывают, какими свойствами обладают, а также отвечу на главный, на мой взгляд, и совершенно правильный вопрос, который часто несправедливо игнорируется в подобных статьях. Звучит он так: А это всё вообще зачем?
Забегая вперед, скажу, что простейшие клеточные автоматы используются в криптографии, моделировании физических процессов, поведения людей, в биологии, и в целой куче других важных и интересных штук. И вообще: во-первых, это красиво.
Я искренне надеюсь, что после прочтения статьи вы сами захотите поиграться с ними, и на этот случай у меня припасен собранный из JS и палок генератор.
Читать полностью »
Как-то я экспериментировал с клеточными автоматами. С одномерными и двумерными. Придумывал на каком исходном состоянии применить какое-то правило. Когда, в качестве исходного состояния двумерного клеточного автомата я начал использовать бит-реверсивную перестановку диагональной линии, то после применения автомата получались своеобразные узоры. Время от времени среди узоров появлялись явно выраженные характерные паттерны. Я выделил эти паттерны и немного с ними поэкспериментировал. С тем, что мне удалось выяснить, я делюсь в этой статье.
В статье я вкратце расскажу про аддитивные клеточные автоматы. А также приведу последовательность моих наблюдений и задач, которые я ставил. Каждый этап будет сопровождаться изображениями состояния клеточного автомата. Кроме того, для лучшей наглядности, я написал веб-приложение, которое добавит интерактивности при чтении статьи. Приложение основано на React и должно работать в современных браузерах. Также я буду сопровождать некоторые действия ссылками с кусками кода на Python.
Disclaimer: Статья носит чисто информационно-развлекательный характер, поскольку мне не известны приложения предлагаемой информации. Также, мне интересно упорядочить обрывочные сведения, которые мне удалось выяснить. И, возможно, обнаружить в них шероховатости. Возможно, мне придут в голову новые эксперименты.
Надеюсь, что статья развлечет вас, хотя я буду писать четко и по делу.
Одним вечером я наткнулся на статью о реализации одномерного клеточного автомата с помощью комонад, однако материал неполон и немного устарел, в связи с чем решил написать русскоязычную адаптацию (заодно рассмотрев двумерные клеточные автоматы на примере Game of Life)
Реализация классического клеточного автомата — конуээвской «Жизни» — это такая же задачка для начинающего программиста, как для радиотехника — спаять простейший радиоприемник. Для тех кто не знает, что такое «Жизнь», прочитайте эту статью: Википедия: Жизнь (игра).
Напомню правила: действие происходит на клеточном поле. Каждая клетка имеет 8 соседей — клетки, примыкающие к ней сторонами или углами. В начале игры некоторые клетки заполнены, образуя начальный организм, остальные — пусты. Эволюция происходит так: в следующем поколении очищаются все заполненные клетки, имеющие менее 2 или более 3 соседей и заполняются пустые, имеющие ровно 3 соседа.
После того, как поиграешь с интересными конфигурациями, становится немного скучно. В самом деле, за 40 лет все, что можно описано, разжевано на сотнях страниц различных статей и книг. Найти что-то новое и интересное сложно. Тогда возникает желание поменять правила — а вдруг новые организмы будут вести себя совершенно по-иному?
