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

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

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

Эволюция
Время изменяется дискретно, такт за тактом.
Состояние клетки в следующий момент времени задается как функция от ее собственного состояния и состояний соседей в текущий момент времени.
Вид этой функции определяет поведение клеточного автомата.

Примеры
Игра «Жизнь»
Соседи устанавливаются или по наличию общих границ у клеток, или с помощью графа

Игра «Жизнь»,
предложенная Дж. Конвеем
Игровое поле состоит из квадратных клеток (каждая клетка имеет 8 соседей).
Клетка может находиться в 2-х состояниях («живом» или «мертвом»).
Если у «живой» клетки 2 или 3 «живых» соседа, она остается живой на следующем такте.
Если у «мертвой» клетки ровно 3 «живых» соседа, она оживает на следующем такте.
Во всех остальных случаях клетка на следующем такте становится «мертвой».

Объекты игры «Жизнь»,
обладающие особым поведением
Устойчивые организмы.
Популяции и вирусы.
Объекты, способные двигаться («глайдеры»).
Хищники.
«Глайдерное ружье».

Клеточные автоматы дают полезные модели для исследований в естественных науках: моделирование роста снежинки
Парообразное состояние – черный цвет (0), лед – другой цвет (1).
У клетки 6 соседей.
Будущее состояние определяется четностью суммы состояний соседей.
Снежинка растет, начиная от одной клетки

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

Структура связей внутри популяции

Состояния клеток
уровни эмоционального состояния;
степени информированности;
варианты мнений;
степени податливости влиянию;
степени усвоения вредных привычек;
и т. д.

Пример: распространение мнений в малом коллективе

Пример: формирование мнений
Мнение определяется большинством влияющих голосов:
сумма влияющих мнений > 0 → 1 (красный цвет),
сумма влияющих мнений < 0 → -1 (синий цвет),
сумма влияющих мнений = 0 → 0 (желтый цвет).
Такт 1
Такт 2

Пример

Ссылки
Филичев С. В. Информатика – это просто!: Учебное пособие. – М.: ЭКОМ, 1999. С.129-134.
Современный компьютер: Сб. науч.-попул. статей. – М.: Мир, 1986. С. 158-173.
http://www.formoza.ru/tech_bred/6 (URL).
http://graphics.cs.msu.su/courses/cg2000b/hw1 (URL).