Не похожие на «Жизнь» клеточные автоматы

Cуществует много других клеточных автоматов совсем не похожих на игру «Жизнь», но тем не менее очень интересных. Про некоторые из них и хочется рассказать здесь.

Начнём с того, что рассмотрим ряд клеток, в которых, кроме одной, находятся нули:

... 0 1 0 0 0 0 0 0 ...

Рассмотри следующее правило, заменяем число в клетке на сумму этого числа и соседа слева. Получим следующую серию состояний:

... 0 1 0 0 0 0 0 0 ...
... 0 1 1 0 0 0 0 0 ...
... 0 1 2 1 0 0 0 0 ...
... 0 1 3 3 1 0 0 0 ...
... 0 1 4 6 4 1 0 0 ...
... 0 1 5 10 10 5 1 0 ...
... 0 1 6 15 20 15 6 1 ...

Не сложно увидеть, что это — треугольник Паскаля. А теперь вместо обычного сложения будем использовать сложение по модулю два. Известно (и даже недавно рассказывалось в хабрастатье Треугольник Серпинского и треугольник Паскаля), что получится дискретный аналог треугольника Серпинского: 

... 0 1 0 0 0 0 0 0 ...
... 0 1 1 0 0 0 0 0 ...
... 0 1 0 1 0 0 0 0 ...
... 0 1 1 1 1 0 0 0 ...
... 0 1 0 0 0 1 0 0 ...
... 0 1 1 0 0 1 1 0 ...
... 0 1 0 1 0 1 0 1 ...

Интересно? Читаем дальше!


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

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

int transformCell( int northWestCell, int northCell, int northEastCell, int westCell, int centerCell, int eastCell, int southWestCell, int southCell, int southEastCell);

Ограниченный и неограниченный рост

Итак, пусть клетки могут находиться в двух состояниях 0 — мёртвая, и 1 — живая.
Рассмотрим следующее правило: клетка становится живой, если хотя бы один из её соседей живой; клетка, однажды став живой, остаётся живой всегда. В случае окрестности Мура тело функции transformCell() будет таким: 

int sum = northWestCell + northCell + northEastCell + westCell + eastCell + southWestCell + southCell + southEastCell; if (sum > 0) { return 1; } else { return centerCell; }

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

 

 

 

 

 

 

Немного изменим правило выше: вместо условия «хотя бы один из соседей живой», рассмотрим условие «в точности один из соседей живой».

int sum = northWestCell + northCell + northEastCell + westCell + eastCell + southWestCell + southCell + southEastCell; if (sum == 1) { return 1; } else { return centerCell; }

Получаемая из одной клетки структура будет, во-первых, гораздо разреженней, а, во-вторых, будет иметь явный фрактальных характер.

Можно вместо окрестности Мура рассмотреть окрестность фон Неймана:

int sum = northCell + westCell + eastCell + southCell; if (sum == 1) { return 1; } else { return centerCell; }

Циклические клеточные автоматы

Циклические клеточные автоматы были придуманы Дэвидом Гриффитом. Клетка может находиться в n состояниях, которые будем нумеровать числами 0, 1, ..., n – 1. Будем говорить, что состояние m является следующим за состоянием k, если m + 1 = k (mod n). Клетка из состояния m переходит в следующее состояние k, только если одна из соседних клеток имеет состояние k. Например, в случае окрестности фон Неймана преобразование запишется следующим образом:

int nextState = (centerCell + 1) % statesNumber; if (northCell == nextState || westCell == nextState || eastCell == nextState || southCell == nextState) { return nextState; } else { return centerCell; }

При этом, если начать со случайно заполненного поля, могут наблюдаться три различных стадии. Первая стадия — случайное поле. Затем начинают появляться цветные области, которые будут поглощать области, заполненные случайно. Эти блоки будут «волнообразно» менять свой цвет. Далее возникают спирали, которые также называют демонами. И наконец, на третьей стадии, поле будет поглощено демонами.

  

  

Можно также рассмотреть одномерный циклический клеточный автомат:

int transformCell(int leftCell, int centerCell, int rightCell) { int nextState = (centerCell + 1) % statesNumber; if (nextState == leftCell || nextState == rightCell) { return nextState; } else { return centerCell; } }

  

Если интересно узнать больше подробностей, то рекомендую начать с википедии Cyclic cellular automaton.

Мешанина

Пусть снова клетка может находиться в состояниях 0, 1, ..., n – 1.
Рассмотрим правило состоящее из трёх частей.

Здоровье. Если клетка находится в состоянии 0 (т. е. здорова), то она заболевает, если несколько из её соседей больны (т. е. находятся в ненулевом состоянии).

Выздоровление. Если клетка находится в состоянии n – 1, то она самовылечивается и переходит в состояние 0.

Болезнь. Иначе же состояние клетки рассчитывается как среднее состояний соседних клеток плюс некоторая константа. (Если полученное число больше чем n – 1, то новым состоянием будет n – 1.)

int sum = northWestCell + northCell + northEastCell + westCell + eastCell + southWestCell + southCell + southEastCell; 
if (centerCell == 0) { 
         if (sum < 5) { return 0; } 
         else if (sum < 100) { return 2; } 
         else { return 3; } 
} 
else if (centerCell == statesNumber - 1) { return 0; } 
else { return Math.min(sum / 8 + 5, statesNumber - 1); }

  

Отмечается, что получаемые таким образом волнообразные процессы, напоминают реакцию Белоусова – Жаботинского.

Поверхность Венеры

Это правило (как впрочем и предыдущее) я нашёл в Cellab Manual. Каждая клетка находится в состоянии 0, 1, 2 или 4. Правило имеет вид:

if (centerCell == 0) { return 2 * ((northWestCell % 2) ^ (northEastCell % 2)) + northCell % 2; } else if (centerCell == 1) { return 2 * ((northWestCell % 2) ^ (southWestCell % 2)) + westCell % 2; } else if (centerCell == 2) { return 2 * ((southWestCell % 2) ^ (southEastCell % 2)) + southCell % 2; } else { return 2 * ((southEastCell % 2) ^ (northEastCell % 2)) + eastCell % 2; }

Если начинать со случайно заполненного поля, то образуется два врезающихся друг в друга «потока»: вертикальный и горизонтальный. Через некоторое время один из «потоков» начинает преобладать. И в итоге остаётся только один.


Гость, оставишь комментарий?
Имя:*
E-Mail:


 
Свежее новое
  • В Москве пройдет один из крупнейших хакатонов в мире в сфере искусственного интеллекта
  • PicsArt, ведущая творческая платформа для создания контента и визуализации историй в социальных сетях с более чем 100 миллионами активных
  • Сильный Искусственный Интеллект «Smart-MES» меняет взгляды на Технологическую Сингулярность
  • Учёные полагают, что Технологическая Сингулярность наступит тогда, когда Сильный Искусственный Интеллект будет способен самостоятельно создавать себе
  • Навыки голосовых помощников от Amazon, Google, Microsoft и Яндекс
  • После лекции директора по маркетингу умного помощника Алисы, Даниилы Колесникова, меня посетило вдохновение и любопытство. Так как мы сами сейчас
  • Конкурс идей от лаборатории Касперского - Kaspersky Start Russia
  • Если ты инициативный лидер, у тебя есть знания в области IT и тебе хотелось бы возглавить собственный проект в лаборатории Касперского, то подай
  • Смарт-города, умный транспорт и инновации для ЖКХ: что обсуждали на конференции «Интернет вещей»
  • Интернет вещей для промышленности, транспорта, ЖКХ и торговли: в Москве обсудили развитие и внедрение технологии. Конференция «Интернет вещей»,
Последние комментарии
5 лучших приложений искусственного интеллекта для вашего телефона Android
какой это искусственный разум мне смешно не пудрите людям мозги ,голосовой поисковик- это интелект ха ха ну вы тут и загибаете фантастику
5 лучших приложений искусственного интеллекта для вашего телефона Android
Всё вышеперечисленное назвать интеллектом можно с большущей натяжкой. Так, программки-автоматы с почти хорошим распознаванием несложной речи.
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
У нас очень странный народ, если что не понимает, то обязательно надо сунуть в морду. Зачем? А не лучше ли поинтересоваться, почему именно так? У
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
Господин Чернов. Поясню. Любой инструмент, даже прозаическая кофемолка, проходят процедуру стендовых испытаний. Сертификат соответствия
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
     " И странная картина получается в коридорах власти ". Странная картина  получается, если полагать, что власть эта поставлена для решения задач
Мы в социальных сетях
Статистика
0  
Всего статей 1533
1  
Всего комментариев 65
0  
Пользователей 56