15x4 - 15 минут про клеточные автоматы

В память о большом математике Джоне Хортоне Конвее (26 декабря 1937 — 11 апреля 2020), который открыл сюрреальные числа, сформулировал гипотезу чудовищного вздора (да-да, это всё строгие математические понятия) и придумал алгоритм Судного дня, мы хотели бы рассказать о самом знаменитом его результате – о придуманной им игре «Жизнь».

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

- если пустая клетка окружена ровно тремя живыми соседями, то в ней зарождается жизнь (правило размножения);

- если у живой клетки два или три живых соседа, она выживает (правило выживания);

- если у живой клетки более трёх живых соседей, она умирает от перенаселения, а если меньше двух – она умирает от одиночества (правила увядания).

Таким образом, расстановка клеток в первом поколении однозначно задаёт то, что будет происходить в игре потом.

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

В игре можно сформулировать много интересных вопросов, например: ? существует ли конечная исходная колония, число потомков которой росло бы бесконечно с каждым шагом??

Правила просты, есть онлайн симуляторы, можете поиграться, например, здесь: https://life.written.ru/

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

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

Источник: www.michurin.net

Комментарии: