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

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

2. Содержание

Клеточные автоматы. Общие сведения.
Пример программирования – Игра
«Жизнь»
2

3. Автоматы

Автоматом называют
устройство (или совокупность
устройств), которое без
непосредственного участия
человека выполняет процессы
приема, преобразования и
передачи энергии, материалов
или информации в
соответствии с заложенной в
него программой.
Центробежный регулятор Дж. Уатта
3

4. Дискретные автоматы

Задается конечные множества А входных
сигналов, Q внутренних состояний и V
выходных сигналов, а также функция
переходов и функция выходов .
Если число возможных значений аргументов
функций также конечно, автоматы называют
конечными.
(Q, A) = Q’
( Q, A) = V
4

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

Клеточные автоматы (КА) являются частным случаем
конечных автоматов, используемых для
моделирования динамического поведения
однородных сред.
При этом пространство и время считаются
дискретными, а физические величины в каждой точке
моделируемой среды могут принимать конечное
множество дискретных значений.
5

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

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

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

Идея близка к тому, как устроены многие явления в природе и технике. Например,
клетки в живом организме взаимодействуют друг с другом по схожему принципу,
реагируя на состояние соседей.
Практическое применение:
Моделирование природных явлений (лесной пожар, рост кристаллов)
Экология и эволюция (модель хищник-жертва)
Моделирование городских систем и транспорта (симуляция движения автомобилей)
Физика и химия (жидкости и газы, реакции на молекулярном уровне)
Ограничения:
Работают на дискретных пространствах
Большая вычислительная сложность для больших сеток
7

8. История КА

Первая клеточно-автоматная
система (40-е г.)
Станислав
Улам
Джон фон
Нейман
Клеточно-автоматная модель
возбудимой среды (40-е г.)
Но́рберт Ви́нер
Артуро Розенблют
8

9. История КА

Цифровая физика:
Вселенная по сути является
информацией и, следовательно,
является вычислимой.
Т.е. Вселенная может пониматься как
результат работы некоторой
компьютерной программы или как
некий вид цифрового вычислительного
устройства
Конрад Цузе
Стивен Вольфрам
Книга A New Kind of Science:
Природу вычислений необходимо
изучать экспериментально
Результаты этих экспериментов имеют
большое значение для понимания
окружающего мира, который
предполагается дискретным.
9

10. Элементарный КА

Одномерный бинарный (с двумя возможными состояниями) клеточный автомат,
где состояние клетки в каждый момент времени зависит только от её
собственного состояния и состояний смежных с ней клеток в предыдущий
момент времени.
Простейших клеточных автоматов существует всего 256, и поведение некоторых
из них дублирует другие. С. Вольфрам предложил называть их числами от 0 до
255. Это именование называется "Код Вольфрама".
Пример: номер правила 110
Переведем в двоичный код 11010 = 011011102
Впишем цифры двоичного представления числа в таблицу:
10

11. Типы поведения КА

Класс 1: Быстро сходится к состоянию из одних нулей или единиц.
Вольфрам приводит как примеры правила 0, 32, 40, 160, 232.
Класс 2: Быстро сходится к циклическому или стабильному состоянию.
Например, правила 3, 4, 33, 108, 218, 250.
Класс 3: Сохраняется в случайном состоянии. Например, правила 22, 30,
126, 150, 182.
Класс 4: Образуются как области с циклическими или стабильными
состояниями, так и структуры, которые взаимодействуют друг с другом
сложными способами. 110, 193
11

12. Типы поведения КА

1 класс: все клетки быстро принимают одинаковое состояние, которое
становится стабильным. Например, Правило 40:
12

13. Типы поведения КА

2 класс: состояние всех клеток быстро стабилизируется, либо возникают
периодические колебания. Например, Правила 3 и 33:
13

14. Типы поведения КА

3 класс: автомат порождает хаотические, непериодические структуры.
Небольшие изменения исходного состояния влекут значительные
изменения в результате. Например, правило 22:
14

15. Типы поведения КА

4 класс: автомат порождает сложные, взаимодействующие между собой
структуры, способные выживать длительное время, однако не достигает
стабильности. Например, правило 193:
Атлас КА С. Вольфрама
http://atlas.wolfram.com/01/01/
15

16. Игра «Жизнь»

Каждая клетка поля в каждый момент (дискретного)
времени считается живой либо мёртвой, причём на
следующем временно́м шаге состояние клетки
определяется следующими правилами, зависящими от
состояния её восьми клеток-соседей на текущем шаге:
Джон Хортон Конвей
если клетка была живой, то она остаётся живой, если у
неё было ровно 2 или 3 живых соседа;
если клетка была мёртвой, то она становится живой,
если у неё было ровно 3 живых соседа.
16

17. Игра «Жизнь»

На поле игры «Жизнь» могут существовать
неподвижные,
стабильно перемещающиеся,
стабильно размножающиеся конфигурации,
логические вентили, позволяющие реализовать в ней произвольное
вычисление (полнота по Тьюрингу), и многие другие нетривиальные
конструкции.
17

18. Игра «Жизнь»

18

19. Задание на дом Автоматы серии "Поколения"

Задание на дом
Автоматы серии "Поколения"
Автоматы с числом состояний более чем два.
Правила изменений состояния клетки записываются следующим образом
S/B/C
где:
S - набор цифр от 0 до 8, определяет число "живых" соседей, при котором
клетка остается "в живых",
B - набор цифр от 0 до 8, определяет число "живых" соседей при котором
"мертвая" клетка становится "живой"
С - число, определяет число ходов "умирания" клетки
19

20. Автоматы серии "Поколения"

Автоматы серии "Поколения"
"Искры"
2/2/25
На рисунке представлены 0-ая, 16-ая, 32-ая, 48-ая, 64ая и 80-ая конфигурации:
20

21. Автоматы серии "Поколения"

Автоматы серии "Поколения"
"Пламя"
235678/3468/9
На рисунке представлены 0-ая, 16-ая, 32-ая, 48-ая, 64ая и 80-ая конфигурации
21