Синергетика и компьютерное моделирование. Игра «Жизнь» Один из подходов к моделированию процессов самоорганизации – «клеточные автоматы» – появился благодаря развитию вычислительной техники, информатики и теории игр. Понятие «клеточные автоматы» было введено в конце сороковых ХХ столетия Дж. фон Нейманом и К. Цусе как дискретная вычислительная среда для построения разнообразных алгоритмов. Клеточные автоматы изобретались много раз, под разными названиями. В математике аналогичные объекты изучались в одном из разделов топологической динамики, а в электротехнике они были известны как итерационные массивы. Дисциплина: Синергетика для инженеров Преподаватель: профессор каф. общей физики Н.Н. Никитенков

Клеточный автомат представляет собой дискретную динамическую систему, поведение которой полностью определяется набором локальных правил. Клеточный автомат состоит из множества объектов-ячеек, образующих регулярную решетку (которая может быть как конечной, так и бесконечной). Состояние любого объекта-ячейки в момент времени t характеризуется некоторой переменной (определенным числом или набором чисел) и изменяется синхронно через дискретные интервалы времени в соответствии с правилами, однозначно определяющими последующее состояние объекта-ячейки в зависимости от состояния переменных в ближайших соседних ячейках. Правила являются всюду одинаковыми, локальными и не изменяются во времени.

Основные свойства клеточных автоматов 1. Локальность правил: на новое состояние объекта-ячейки влияет лишь она сама и ее соседи. Действия на расстоянии нет. 2. Однородность системы: ни одна область решетки не отличается от другой (но если решетка конечна, то возможны краевые эффекты). 3. Множество возможных состояний клетки конечно. Это условие необходимо, чтобы для получения нового состояния клетки требовалось конечное число операций. 4. Значения во всех клетках изменяются одновременно, в конце операции. Конечно, и сама решетка, на которой развертывается процесс, и правила, которым он подчиняется, могут быть различными, следовательно, клеточные автоматы также будут обладать разными свойствами и демонстрировать различное поведение.

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

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

Игра «Жизнь» Пространством, на котором развертывается игра «Жизнь», является плоскость, разделенная на квадратные ячейки. Размеры плоскости (количество ячеек по вертикали и горизонтали) могут быть различными. Чаще всего рассматривают бесконечную плоскость. Клетка считается «живой», если на ней находится фишка, «пустая» клетка считается «мертвой». Время в игре «Жизнь» дискретно и измеряется в поколениях: каждый момент дискретного времени (t=1,2,…) соответствует одному поколению (1,2,…). Рождение и гибель клетки в момент времени t+1 определяется состоянием ее соседей в момент t. У каждой клетки имеется 8 соседей, из них 4 имеют с ней общие грани, а 4 имеют с ней общие вершины.

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

а) б) в) Эволюция триплета «семафор»: а – исходный триплет в первом поколении; б – первое поколение, с указанием гибнущих и рождающихся клеток; в – конфигурация «семафор» во втором поколении. Из правил игры следует, что верхняя и нижняя клетки триплета погибают. Центральная же клетка имеет двух живых соседей, поэтому она выживает и переходит в следующее поколение. А на двух клетках, прилегающих к триплету, рождается в следующем поколении новая жизнь. Другие примеры см. в пособии