Авторизация

Забыли пароль?

Регистрация >>

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

10-05-2010 (14:53) - Daniel

В настоящем мужчине скрыто дитя, которое хочет играть.
Фридрих Вильгельм Ницше

Введение

      В греческой мифологии механизмом Вселенной являлись боги. Они самолично тащили солнце по небу, посылали дождь и гром и вкладывали подходящие мысли в человеческие головы. Согласно более новым представлениям, мир создан завершенным, т.е. вместе с механизмом его функционирования; будучи однажды приведен в движение, он продолжат двигаться сам собой. Бог сидит снаружи и наслаждается наблюдением за ним.

     Клеточные автоматы являются стилизованными, синтетическими мирами, определенными простыми правилами, подобные правилам настольной игры. Они имеют свой собственный вид материи, которая кружится в своих собственных пространстве и времени. Можно вообразить удивительное разнообразие этих миров. Можно действительно построить их и наблюдать, как они развиваются. Поскольку, творцы мы начинающие, вряд ли у нас получится создать интересный мир с первой попытки.
      Машина клеточных автоматов является синтезатором миров. Подобно органу, она имеет клавиши и регистры, с помощью которых возможности инструмента можно приводить в действие, комбинировать и перекомпоновывать, а ее цветное окно является окном, через которое можно наблюдать мир, который сейчас «играется».
 Клеточные автоматы изобретались много раз под разными названиями, и несколько отличающиеся друг от друга понятия употреблялись под одним и тем же названием. В чистой математике их можно обнаружить как один из разделов топологической динамики, в электротехнике они иногда называются итеративными массивами, а студенты могут знать их как вид игры на домашнем компьютере. Их использовали и злоупотребляли ими не только междисциплинарные ученые, но и междисциплинарные болтуны. Они стали темой или поводом бесчисленных диссертаций. О них много говорилось и писалось, но до последнего времени никто в действительности не видел большинство из них
      Клеточные автоматы ввел в конце сороковых годов Дж. Фон Нейман, следуя идее С. Улама, для того, чтобы обеспечить более реалистичные модели поведения сложных, пространственно протяженных систем; в клеточном автомате и объекты, которые могут быть интерпретированы как пассивные данные, и объекты, которые могут быть интерпретированы как вычислительные устройства, собираются из одного типа структурных элементов и подчиняются одни и тем же «мелкозернистым» законам; вычисление и конструирование являются просто двумя возможными типами активности.
     Хотя фон Нейман был ведущим физиком  в такой же степени, как и математиком, точные физические рассуждения отсутствуют в его работе по клеточным автоматам; его больше интересовало редукционистское объяснение определенных аспектов биологии. Действительно, механизмы, которые он предложил для получения самовоспроизводящихся структур на клеточном автомате, сильно напоминают открытые в пятидесятых годах механизмы, которые на самом деле наблюдаемы в биологических системах.
     Клеточные автоматы могут моделировать феноменологические аспекты нашего мира, такие как общение, вычисление и конструирование; рост, воспроизведение, конкуренция, эволюция.
     В клеточных автоматах пространство и время дискретны, а физические величины принимают конечное множество дискретных значений. В частности, как разновидность клеточных автоматов можно рассматривать модель формирования общественного мнения [1, 2].

Клеточный автомат своими руками

     Возьмите стопку миллиметровки или другой разграфленной на клетки бумаги хорошего качества, в которой сетка напечатана в точности на том же месте на каждом листе. Начиная с последнего листа и проходя стопку в обратном направлении, Вы должны нарисовать серию кадров, по одному на каждом листе, которые составят краткую мультипликационную последовательность.
     Откройте стопку на последнем листе и нарисуйте простую картинку, заполняя несколько клеток сетки рядом с центром; это будет первый кадр Вашего мультипликационного фильма. Переверните страницу, наложив предпоследний лист на последний; рисунок первого кадра будет просвечивать сквозь бумагу. Нарисуйте очередной кадр на новом листе, соблюдая правило INKSPOT:
выберите клетку и посмотрите на область 3x3, центром которой она является, - ее «окрестность». Если Вы увидите в этой области (на листе, находящемся прямо под этим) в точности три черные клетки, пометьте слегка вашу клетку карандашом;  также пометьте эту клетку, если она находится непосредственно над черной клеткой.
     Сделайте тоже самое для каждой клетки решетки. По окончании закрасьте чернилами все отмеченные клетки.
Постройте третий кадр из второго, обращаясь к следующему листу и применяя тот же способ; затем постройте четвертый кадр из третьего и так далее, пока не будут использованы все листы.
     Теперь Вы можете на ваш блокнот. Сложите стопку, захватив ее край между большим и указательным пальцами, и пусть листы падают один за другим в быстрой последовательности. То, что Вы увидите, является чернильным пятном, которое проступает нерегулярно – как на грязной материи – порождая мысы и заливы, оставляя незначительное число маленьких областей нетронутыми и время от времени выбрасывая прямые нити (рис. 1).


Рис. 1.

Кадры последовательности INKSPOT

     Это в сущности все, что нужно для клеточного автомата. Измените начальные условия, и Вы получите несколько иную картинку. Измените рецепт, и Вы получите новое множество динамических законов – новый мир. Вы можете использовать сетку иной формы (может, гексагональную или трехмерную). Рецепт может относиться к окрестности с другой формой и размером, отличным от 3х3 и может включать чернила более чем одного цвета.
     Если лист будет состоять из 100 000 клеток, то потребуется один день работы, чтобы нарисовать новый кадр. Применение информационных технологий и современных языков программирования позволяет генерировать новые кадры и воспроизводить их со скоростью показа слайдов.

Игра «Жизнь»

      Игра математика Джона Конвея «Жизнь», придуманная им в 1970 году – клеточный автомат. Игровое пространство – «вселенная» - размеченная на клетки поверхность, она может быть ограниченной, безграничной или замкнутой. Джон Конвей упростил слишком сложную математическую модель машины, воспроизводящей саму себя, придуманную Джоном фон Нейманом. В итоге, ему удалось разработать правила, которые стали правилами игры «Жизнь», впервые описание этой игры было опубликовано в октябрьском выпуске журнала Scientific American в 1970 году, в рубрике «Математические игры» Мартина Гарднера.
     Каждая клетка игрового пространства окружена 8-и такими же клетками (окрестность Мура). Каждая клетка может находиться в двух состояниях – живом (закрашенном) или мертвом, (пустом). На состояние любой клетки оказывают влияние состояние соседних клеток. Во времени эти состояния дискретно в соответствии с некоторыми правилами или генетическими законами Конвея, состоящими из 2 пунктов:
       1)    ВЫЖИВАНИЕ ИЛИ ГИБЕЛЬ. Если живая клетка имеет меньше 2 или более 3 соседей в окрестности из 8 клеток то в следующем поколении она умирает (моделирование реальных условий - недостатка питания или перенаселенности), в противном случае она выживает;
        2)    РОЖДЕНИЕ. В пустой клетке появляется живая клетка, если у исходной клетки ровно 3 соседа.
     Гибель и рождение всех организмов происходит одновременно.
     Возникающие в игре ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели живых организмов.
    Игра "Жизнь" относится к категории так называемых моделирующих игр - игр, которые в той или иной степени имитируют процессы, происходящие в реальной жизни (зарождение, развитие и гибель живых организмов, цивилизаций, популяций)
     Данная игра сильно повлияла на развитие многих разделов математики и информатики: теория автоматов, теория алгоритмов, теория игр, алгебра и теория чисел, теория вероятностей, комбинаторика и теория графов, фрактальная геометрия, вычислительная математика.
     Многие закономерности, обнаруженные в этой игре, имеют аналоги в других дисциплинах: кибернетика (самовоспроизводящиеся системы), биология (развитие популяций примитивных организмов), физиология (рождение и смерть клеток аналогичны процессу возникновения и исчезновения нейронных импульсов), астрономия (эволюция сложных колоний повторяют этапы развития спиралевидных галактик), разные разделы физики (процессы столкновения элементарных частиц, анализ диффузии, вязкости и теплопроводности), наномеханика, электротехника, химия, социология, теология, философия и др.

Компьютерная реализация

     Простейший алгоритм последовательно просматривает все ячейки решетки и для каждой ячейки подсчитывает соседей, определяя судьбу каждой клетки (не изменится, умрет, родится). Такой простейший алгоритм использует два двумерных массива — один для текущего поколения, второй — для следующего. Более сложный, но и более быстрый алгоритм составляет списки клеток для просмотра в последующем поколении; клетки, которые не могут измениться, в списки не вносятся. Например, если какая-либо клетка и ни одна из ее соседей не поменялись на предыдущем ходу, то эта клетка не поменяется и на текущем ходу.
     Свою программную реализацию игры «Жизнь» предлагает один из пользователей Genius Land, студент МГУ им. Ломоносова Баранов Михаил, релиз скомпилированного программного кода, написанного на современном языке программирования высокого уровня C# (читается как си шарп) Вы можете скачать по этой ссылке. Для работы программы вам потребуется Net Framework версии не ниже 3.5, который можно скачать по этой ссылке.
     В программе можно задавать размер игрового поля, перемещение по которому осуществляется путем нажатия на клавиши: W, A, S, D – вперед, влево, назад, вправо, соответственно. В игре так же можно задать количество колоний (популяций) от 1 до 3, которые будут окрашены в красный, зеленый и синий цвета.
     После опубликования правил игры «Жизнь», она пользовалась огромной популярностью, близкой к  культу, и сделала выражение «клеточные автоматы» частью бытового жаргона целого поколения молодых ученых. Вскоре игроки стали обнаруживать интересные шаблоны (варианты расстановки живых клеток в первом поколении), самые известные из них: планер (glider) и планерное ружье Госпера – первая бесконечно растущая фигура (рис. 2 и 3).

Рис.2. Планер

Рис.3. Планерное ружье


      Некоторые фигуры остаются неизменными во всех последующих поколениях, состояние некоторых может изменятся или повторятся, через определенное количество поколений. Например, существует фигура Diehard потомки которой существуют 130 поколений, а затем исчезают.
      Первоначально самим создателем игры было сделано предположение, что никакая начальная комбинация живых клеток не может привести к неограниченному размножению и предложил премию в 50 долларов тому, кто подтвердит или опровергнет эту гипотезу. Приз был получен командой из Массачусетского технологического института, придумавшей неподвижную повторяющуюся фигуру, которая периодически создавала движущиеся «планеры». Таким образом количество живых клеток росло до неограниченного.
     К настоящему времени сложилась следующая классификация фигур:
•    Устойчивые фигуры: фигуры, которые остаются неизменными
•    Периодические фигуры: фигуры, у которых состояние повторяется через некоторое число поколений
•    Двигающиеся фигуры: фигуры, у которых состояние повторяется, но с некоторым смещением
•    Ружья: фигуры, у которых состояние повторяется, но дополнительно появляется двигающаяся фигура
•    Паровозы: двигающиеся фигуры, которые оставляют за собой следы в виде устойчивых или периодических фигур
•    Пожиратели: устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами
     Райским садом (рис. 4) называется такое расположение клеток, у которого не может быть предыдущего поколения.

Рис. 4. Пример райского сада


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

Литература

1.  K.Kaspersky, J.A.Holyst// Physica A. 2000. v.287. p.631.
2.  K.Kaspersky, J.A.Holyst// Physica A. 1999. v.269. p.511.
3. S.Wolfram ed. Theory and Applications of Cellular Automats. Singapore:World Scientific. 1986.
4. Тоффоли Т., Марголус Н. Машины клеточных автоматов: Пер. с англ. - М.: Мир, 1991 - 280 с., ил.
5. Материалы сайта Википедия - версия энциклопедии на русском языке.

 

Грязнев Данил

Михали Баранов

Рейтинг: +2 Голосов: 2

Загрузка комментари ев...

« Назад

Грязнев Данил © 2010