Рубрика «клеточный автомат»

В мире существует около 14 000 видов муравьёв, каждый из которых имеет собственное название. Но, даже если вы зададитесь такой целью, вы не найдёте ни в одном биологическом справочнике муравья Лэнгтона. Дело в том, что этот муравей — математическая абстракция, модель для описания поведения динамической системы. Иногда кажется, что математики вообще неравнодушны к муравьям — вспомним хотя бы уже ставший классическим муравьиный алгоритм. Да и во всяких логических моделях и задачах муравьи встречаются довольно часто.

От хаоса к строгому порядку

Читать полностью »

Жизнь Джона Конвея

Полагаю, всем программистам хорошо известен клеточный автомат жизнь (или эволюция), придуманный английским математиком Джоном Конвеем в 1970 году. Возможно, некоторые даже корпели над самописной программой, моделирующей клеточный автомат Конвея.Читать полностью »

Логика сознания. Часть 1. Волны в клеточном автомате - 1 Начнем разговор о мозге с несколько отвлеченной темы. Поговорим о клеточных автоматах. Клеточный автомат – это дискретная модель, которая описывает регулярную решетку ячеек, возможные состояния ячеек и правила изменений этих состояний. Каждая из ячеек может принимать конечное множество состояний, например, 0 и 1. Для каждой из ячеек определяется окрестность, задающая ее соседей. Состояние соседей и собственное состояние ячейки определяют ее следующее состояние.
Наиболее известный клеточный автомат – это игра «Жизнь». Поле в игре «Жизнь» состоит из ячеек. Каждая ячейка имеет восемь соседей. Задается начальная комбинация. Затем начинается смена поколений. Если у занятой ячейки два или три занятых (живых) соседа, то ячейка продолжает жить. Если соседей меньше 2 или больше 3, то ячейка умирает. Когда у пустой ячейки оказывается ровно 3 соседа в ней зарождается жизнь. Задав произвольную начальную комбинацию можно пронаблюдать ее эволюцию.
Читать полностью »

Этот мир просто охренеть какой сложный, каждый день поражаюсь.

Чтобы хоть как-то его познавать и при этом не съехать с катушек, нам, людишкам, с нашими жалкими мозгами приходится задумчиво смотреть на происходящее, анализировать увиденное и строить модели — абстракции, с помощью которых мы с некоторой точностью кое-что иногда можем предсказывать и даже наивно полагать, что понимаем, что же на самом деле происходит.

И знаете, что удивительно? Этот подход замечательно работает. Ну, почти всегда. По крайней мере, ничего лучше мы до сих пор не придумали.

Но вообще-то я не об этом. Я хочу рассказать об одной чрезвычайно интересной как с эстетической, так и с математической точки зрения категории этих самых моделей.

image

Да, я о клеточных автоматах, а именно — об их подмножестве, простейших клеточных автоматах (Elementary cellular automaton). В этой статье я поведаю, что это такое, какие они бывают, какими свойствами обладают, а также отвечу на главный, на мой взгляд, и совершенно правильный вопрос, который часто несправедливо игнорируется в подобных статьях. Звучит он так: А это всё вообще зачем?

Забегая вперед, скажу, что простейшие клеточные автоматы используются в криптографии, моделировании физических процессов, поведения людей, в биологии, и в целой куче других важных и интересных штук. И вообще: во-первых, это красиво.

Я искренне надеюсь, что после прочтения статьи вы сами захотите поиграться с ними, и на этот случай у меня припасен собранный из JS и палок генератор.
Читать полностью »

Эксперименты с бит реверсными паттернами в двумерных аддитивных клеточных автоматах
Как-то я экспериментировал с клеточными автоматами. С одномерными и двумерными. Придумывал на каком исходном состоянии применить какое-то правило. Когда, в качестве исходного состояния двумерного клеточного автомата я начал использовать бит-реверсивную перестановку диагональной линии, то после применения автомата получались своеобразные узоры. Время от времени среди узоров появлялись явно выраженные характерные паттерны. Я выделил эти паттерны и немного с ними поэкспериментировал. С тем, что мне удалось выяснить, я делюсь в этой статье.

В статье я вкратце расскажу про аддитивные клеточные автоматы. А также приведу последовательность моих наблюдений и задач, которые я ставил. Каждый этап будет сопровождаться изображениями состояния клеточного автомата. Кроме того, для лучшей наглядности, я написал веб-приложение, которое добавит интерактивности при чтении статьи. Приложение основано на React и должно работать в современных браузерах. Также я буду сопровождать некоторые действия ссылками с кусками кода на Python.

Disclaimer: Статья носит чисто информационно-развлекательный характер, поскольку мне не известны приложения предлагаемой информации. Также, мне интересно упорядочить обрывочные сведения, которые мне удалось выяснить. И, возможно, обнаружить в них шероховатости. Возможно, мне придут в голову новые эксперименты.

Надеюсь, что статья развлечет вас, хотя я буду писать четко и по делу.

Читать полностью »

Одним вечером я наткнулся на статью о реализации одномерного клеточного автомата с помощью комонад, однако материал неполон и немного устарел, в связи с чем решил написать русскоязычную адаптацию (заодно рассмотрев двумерные клеточные автоматы на примере Game of Life)

life_anim
Читать полностью »

Реализация классического клеточного автомата — конуээвской «Жизни» — это такая же задачка для начинающего программиста, как для радиотехника — спаять простейший радиоприемник. Для тех кто не знает, что такое «Жизнь», прочитайте эту статью: Википедия: Жизнь (игра).

Напомню правила: действие происходит на клеточном поле. Каждая клетка имеет 8 соседей — клетки, примыкающие к ней сторонами или углами. В начале игры некоторые клетки заполнены, образуя начальный организм, остальные — пусты. Эволюция происходит так: в следующем поколении очищаются все заполненные клетки, имеющие менее 2 или более 3 соседей и заполняются пустые, имеющие ровно 3 соседа.

После того, как поиграешь с интересными конфигурациями, становится немного скучно. В самом деле, за 40 лет все, что можно описано, разжевано на сотнях страниц различных статей и книг. Найти что-то новое и интересное сложно. Тогда возникает желание поменять правила — а вдруг новые организмы будут вести себя совершенно по-иному?

Клеточные автоматы на Dart

Читать полностью »

Представьте, что мир — это концертный зал, а ваш только что запущенный стартап — это шоу, которое секунду назад завершилось, и публика вот-вот начнёт рукоплескать вам стоя, либо отделается вялыми хлопками в разных углах зала. Почему по-настоящему гениальные спектакли искушённая публика иногда встречает сдержанно и даже холодно, а некоторые посредственные — криками «Браво»? Как сделать так, чтобы ваш стартап оценили по достоинству, и даже лучше? Как заставить мир аплодировать вам стоя?

image

Профессор Мичиганского Университета Scott E. Page, известный по курсу Model Thinking на Coursera, в соавторстве с John H. Miller в 2004 году предложили изящную модель «Standing Ovations», которая с помощью клеточного автомата описывает, будет ли зал аплодировать стоя, в зависимости от некоторых факторов. В этой статье я сначала опишу модель максимально упрощённо, а затем, под катом, перейду к небольшим математическим и околоматематическим выкладкам, к построению клеточного автомата, а в конце — к выводам применительно к стартапу и другим сферам жизни.

На секунду представьте себя в зрительном зале в волнительный момент опускания занавеса. Что может заставить вас встать и начать аплодировать? Во-первых, разумеется, вам должен понравиться спектакль. Во-вторых, вы, скорее всего, будете чувствовать себя неловко, если окажетесь единственным человеком в зале, аплодирующим стоя (равно как и если все вокруг встанут, а вы будете сидеть). Значит, необходимо, чтобы некоторая часть аудитории уже решила встать. В-третьих, если вы пришли на спектакль с друзьями или семьёй, и кто-то из них встал, то вы, вероятно, захотите его поддержать и встанете тоже. В-четвёртых, вам виден не весь зал. В зависимости от места, которое вы занимаете, вам могут быть видны только первые ряды партера, половина зала или, если вы сидите в первом ряду, то вообще никто кроме ваших соседей. Следовательно, в первую очередь на ваше решение влияет только та часть зала, которая вам видна.

Таким образом, можно выделить четыре фактора, влияющих на то, встанете ли вы:

  1. Ваше впечатление от шоу;
  2. Доля аудитории, которая уже решила встать;
  3. Поведение ваших соседей по ряду;
  4. Поведение «звёзд», сидящих в первых рядах;

Читать полностью »

За последнюю неделю Хабр пополнился сразу несколькими статьями об игре «Жизнь». Что ж, тогда и я поделюсь своими наработками по этой теме.

Предисловие

Минувшим летом мне довелось побывать на летней школе по параллельному программированию, проводимой НГУ. В рамках школы каждый студент должен был подготовить какой-либо проект по одной из тематик, озвученных на лекциях. Меня заинтересовали клеточные автоматы. У меня первая ассоциация при фразе «клеточный автомат» это именно «Жизнь».
Я понимал, что никому не будет интересно наблюдать за черными клеточками, живущими на экране. Да и слишком просто это для такого проекта. Нужно было придумать что-то принципиально новое. Я решил расширить диапазон своих мыслей и выйти за пределы двухмерного пространства. В прямом смысле. Я подумал, а почему бы не сделать эту игру трехмерной? Ведь это гораздо интереснее!
Читать полностью »

Есть прекрасная игра/алгоритм «Conway's Game of Life» [wiki] — это набор правил для клеточного автомата который определяет жизнь колонии. Алгоритм был придуман английским математиком в далеком 1970 году.
Игровое поле — квадратная сетка неограниченного размера.
Каждая клетка может иметь два значения Живая или Мертвая
Игрок задает начальное положение клеток на поле и потом наблюдает как они эволюционируют.

Правил эволюции всего 4 и звучат они так:

  1. Живая клетка у которой меньше двух соседей умерает от одиночества.
  2. Живая клетка у которой 2 или 3 соседа живет до следующего хода.
  3. Живая клетка у которой больше 3 соседей умирает от перенаселения.
  4. Мертвая клетка у которой ровно 3 живых соседа становаится живой (рождается).

Соседними считаются клетки по вертикали, горизонтали и диагонали. Т.е. у одной клетки может быть восемь соседей.

Эти простые правила позволяют реализовать машину Тьюринга и даже простые колонии (наборы живых клеток) могут обладать очень интересными свойствами.

Реализация игры «Life 1970» на javascriptе с использованием TTD

Я решил реализовать алгоритм на джаваскрипте с ипользованием TTD и рассказать об этом.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js