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

Клеточные автоматы. Часть III. Применение клеточных автоматов

Теория клеточных автоматов, связанная с именами фон Неймана и Конрада Цузе, имеет фундаментальное значение для всей науки и многообразное прикладное применение. Начиная с работ Т. Тоффоли и Н. Марголуса 80-х гг. [Тоффоли и др.

1991], клеточные автоматы (КА) стали использоваться в моделях физико-химических процессов. К середине 90-х гг. клеточно-автоматное моделирование проникло [Pintoetal. 2007] в гуманитарные науки при изучении мультиагентных cистем в урбанистике (толпа, транспортная пробка). Обзорная статья [Ванаг, 1999] В.

Обратите внимание

Ванага по вероятностным КА еще раз легитимизировала для отечественных исследователей клеточные автоматы как метод математического моделирования.

Последнее десятилетие ознаменовалось бумом публикаций в самых разных разделах науки, связанных с КА-моделями [Лобанов, 2010]; одновременно с этим продолжает развиваться и математическая теория клеточных автоматов (на русском языке см. монографию В. Аладьева [Аладьев, 2009]).

Влияние на развитие наук

Хотя игра состоит всего из двух простых правил, тем не менее она более сорока лет привлекает пристальное внимание учёных. Игра «Жизнь» и ее модификации повлияла (в ряде случаев взаимно) на многие разделы таких точных наук как математика, информатика, физика. Это, в частности:

  • Теория автоматов,
  • Теория алгоритмов,
  • Теория игр и математическое программирование,
  • Алгебра и теория чисел,
  • Теория вероятностей и математическая статистика,
  • Комбинаторика и теория графов,
  • Фрактальная геометрия,
  • Вычислительная математика,
  • Теория принятия решений,
  • Математическое моделирование.

Кроме того, многие закономерности, обнаруженные в игре, имеют свои аналогии в других, подчас совершенно «нематематических» дисциплинах. Вот список наук, теории которых имеют интересные точки соприкосновения с феноменами «Жизни»:

  • Кибернетика. Сама игра является удачной попыткой Конвея доказать существование простых самовоспроизводящихся систем.
  • Биология. Внешнее сходство с развитием популяций примитивных организмов впечатляет.
  • Физиология. Рождение и смерть клеток аналогичны процессу возникновения и исчезновения нейронных импульсов, которые и формируют процесс мышления. А также аналогичны созданию импульсов в нервной системе многоклеточных организмов.
  • Астрономия. Эволюции некоторых сложных колоний удивительным образом схематично повторяют этапы развития спиралевидных галактик.
  • Физика твёрдого тела. Теория автоматов вообще и игра «Жизнь» в частности используются для анализа «явлений переноса» — диффузии, вязкости и теплопроводности.
  • Квантовая физика. Поведение «жизненных» ячеек (рождение новых и взаимное уничтожение) во многом напоминают процессы, происходящие при столкновении элементарных частиц.
  • Наномеханика. Стационарные и пульсирующие колонии являются показательным примером простейших устройств, созданных на основе нанотехнологий.
  • Электротехника. Правила игры используются для моделирования самовосстанавливающихся электрических цепей.
  • Химия. Конфигурации, подобные строящимся в игре, возникают во время химических реакций на поверхности, в частности в опытах М. С. Шакаевой возникают движущиеся молекулярные конструкции аналогичные «жизненному» планеру. Также предпринимаются попытки объяснить периодические химические реакции с помощью многомерных клеточных автоматов. Самоорганизацией элементарных частиц также занимается супрамолекулярная химия.
  • Социология. Процессы доминации, вытеснения, поглощения, сосуществования, слияния и уничтожения популяций во многих аспектах схожи с явлениями, происходящими при взаимодействии больших, средних и малых социальных групп.
  • Философия. Приведённый список примеров снова наводит на мысль, что всё во Вселенной развивается по одним и тем же нескольким фундаментальным законам, пока ещё не познанным человеком.

Возможно, эта игра связана и с другими научными явлениями, в том числе и с теми, о которых современной науке пока неизвестно. Также возможно, что не открытые на сегодня законы Природы и Общества станут более понятными благодаря «Жизни» и ее модификациям.

Пожалуй наиболее частое и развитое направление применения клеточных автоматов — это математическое моделирование динамических процессов.

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

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

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

Разумеется, этот подход не является панацеей и имеет наряду с достоинствами ряд серьезных недостатков. Поэтому тем более важно выяснить, какова «экологическая ниша» таких моделей, в частности, в газовой динамике.

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

Важно

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

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

Одной из первых удачных попыток такого рода был “НРР-газ” (названный по первым буквам фамилий своих создателей). Поле этого клеточного автомата представляет собой ортогональную решетку (2-х или 3-х мерную).

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

Столкновения частиц считаются абсолютно упругими.

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

Тем не менее, двумерный вариант этого, автомата имеет один недостаток, который в некоторых случаях является существенным: его макродинамическое поведение не удовлетворяет уравнению Навье-Стокса.

Этого недостатка лишен автомат «ТИР-газ», поле которого – гексагональная решетка, образованная равносторонними треугольниками. Более высокий порядок симметрии обеспечивает выполнение уравнения Навье-Стокса для этого клеточного автомата. С другой стороны, особая структура поля несколько усложняет его реализацию на компьютере и замедляют вычисления.

Газ, описываемый данным клеточным автоматом, естественно, является идеальным, т. е. взаимодействие между частицами сводится к упругим столкновениям.

Совет

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

Между тем, при решении подобных задач с помощью разностных методов возникают трудности, подчас непреодолимые, и использование в этом случае клеточных автоматов могло бы быть вполне уместным.

Одним из существенных недостатков всех этих моделей является их принципиальная изотермичность.

Решеточные газы не являются единственным классом клеточных автоматов при помощи которых можно моделировать процессы в газах.

Подробнее в автореферате диссертации “Применение клеточных автоматов для математического моделирования динамических процессов” 

Степанцов М.Е.

Моделирование неоднородных динамических систем

Также кандидат физико-математических наук Мамзин Е. А. в 2011 году предложил метод клеточных автоматов в качестве высокопроизводительного средства вычисления и развития численных методов.

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

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

В настоящее время наибольшее применение клеточные автоматы нашли в задачах моделирования гидро- и газодинамических, эволюционных, поведенческих, колебательных и различных вероятностных процессов, что обусловлено сравнительной простотой их реализации, предрасположенностью к распараллеливанию и большими перспективами дальнейшего использования. Вопросам применения клеточных автоматов посвящены исследования многих отечественных и зарубежных учёных. Среди них МалинецкийГ.Г., Шакаева М.С., Лобанов А.И., Биндера К., von Neumann J., Martin O.,Toffoli T., Margolus N., Wolfram S., Moore F., Cipra B., Gacs P., Gardner M.,Gutowitz H. и др.

Однако известные клеточные автоматы не обладают достаточным быстродействием для моделирования неоднородных динамических систем задач в больших масштабах и на подробных сетках. Поэтому совершенствование данного численного метода является весьма перспективным.

Источник: https://neuronus.com/theory/ca/654-kletochnye-avtomaty-chast-iii-primenenie-kletochnykh-avtomatov.html

Ознакомительный урок на тему “Одномерные клеточные автоматы”

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

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

    1.1. Основные свойства классической модели клеточных автоматов

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

      Класс 1: Развитие происходит с конечным числом итераций до уникального однородного состояния, то есть до определенной точки.

      Класс 2: Генерируются регулярные, периодические узоры, переходящие в предельный цикл.

      Обратите внимание

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

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

      По утверждению Вольфрама эта классификация не совершенна, хотя и является основной и наиболее распространенной. Задача классификации правил по-прежнему остается открытой, о чем свидетельствуют проводимые исследования в динамических системах.

        В одномерном (линейном) клеточном автомате решетка это последовательность клеток, то есть одномерный массив, в котором для каждой из них, кроме крайних, имеется по два «соседа».

        Три клетки (центральная, предыдущая, следующая) порождают  комбинаций состояний этих трёх клеток. Всего существует  возможных правил. Эти 256 правил кодируются в соответствии с  — стандартному соглашению, правилу, которое было предложено .

        Для устранения краевых эффектов решетка «заворачивается» в тор. Это позволяет использовать следующее соотношение для всех клеток автомата:

        y'[i] = f(y[i-1], y[i], y[i+1]),

        где f – функция переходов клетки;

        y'[i] – состояние i-й клетки в следующий момент времени;

        y[i-1] – состояние (i-1)-й клетки в данный момент времени;

        y[i] – состояние i-й клетки в данный момент времени;

        y[i+1] – состояние (i+1)-й клетки в данный момент времени.

        В качестве примера показан результат работы клеточного автомата, реализованный по правилу 161 (10100001). Мы получили фрактал с последовательно вложенной структурой – ковер Серпинского. Правило определяет, что клетка становится черной, когда левая, либо правая, но не обе вместе окрашены в черный цвет.

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

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

          В двумерном (плоскостном) клеточном автомате решетка реализуется двумерным массивом. В ней каждая клетка имеет восемь «соседей» (окрестность из восьми клеток). Для устранения краевых эффектов решетка так же, «заворачивается» в тор. Это позволяет использовать следующее соотношение для всех клеток автомата:

          y'[i][j] = f(y[i][j], y[i-1][j], y[i-1][j+1], y[i][j+1], y[i+1][j+1], y[i+1][j], y[i+1][j-1], y[i][j-1], y[i-1][j-1]).

          Наиболее известным из двумерных клеточных автоматов является автомат, моделирующий игру «Жизнь». В этом автомате, как и во всех, рассмотренных выше, клетки могут находиться в двух состояниях. Функция переходов клеток реализует следующие условия:

          Читайте также:  Стивен хокинг предупреждает - искусственный интеллект может положить конец человечеству

          • если данная клетка мертва (находится в состоянии «ноль»), то она оживет (перейдет в состояние «единица») при условии, что у нее имеется ровно три живых соседа;

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

            Теория клеточных автоматов, связанная с именами фон Неймана и Конрада Цузе, имеет огромное значение для всей науки и многообразное прикладное применение. Клеточные автоматы с 80-х гг. используются в моделях физико-химических процессов, с 90-х гг. в гуманитарных науках, таких как урбанистика (толпа, транспортная пробка). Обзорная статья В.

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

            Теория клеточных автоматов имеет широкое применение, рассмотрим некоторые из них.

            4.1.Влияние на развитие наук.

              Источник: https://infourok.ru/oznakomitelniy-urok-na-temu-odnomernie-kletochnie-avtomati-972314.html

              Обзор клеточных автоматов

              Книга Т. Тоффоли и Н.

               Марглоуса «Машины клеточных автоматов», вышедшая в 1987 году, посвящена одной такой машине «Сам-6» (специальному устройству для компьютеров IBM PC) и результатам моделирования на ней различных физических процессов, и сегодня утратила актуальность. Однако основные сведения о клеточных автоматах из вводной части, опубликованные здесь, всё равно могут быть интересны широкому кругу читателей.

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

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

              Бог сидит снаружи и наслаждается наблюдением за ним.

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

              Можно вообразить удивительное разнообразие этих миров. Можно действительно построить их и наблюдать, как они развиваются.

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

              Важно

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

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

              Как отмечено во введении, клеточный автомат может мыслиться как стилизованный мир.

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

              Если задан подходящий набор правил (рецепт), то такой простой операционный механизм достаточен для поддержания целой иерархии структур и явлений.

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

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

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

              В обычных моделях вычислений, таких как машина Тьюринга, различают структурную часть компьютера, которая фиксирована, и данные, которыми компьютер оперирует — они являются переменными. Компьютер не может оперировать своей собственной «материальной частью»; он не может себя расширять или модифицировать, строить другие компьютеры.

              Совет

              Клеточные автоматы ввел в конце сороковых годов Джон фон Нейман, следуя идее Станислава Улама, для того чтобы обеспечить более реалистические модели поведения сложных, пространственно протяженных систем; в клеточном автомате и объекты, которые могут быть интерпретированы как пассивные данные, и объекты, которые могут быть интерпретированы как вычислительные устройства, собираются на одного типа структурных элементов и подчиняются одним и тем же «мелкозернистым» законам; вычисление и конструирование являются просто двумя возможными типами активности.

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

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

              В конце войны, когда фон Нейман создавал один из первых электронных компьютеров, немецкий инженер К.

               Цусе прятался от нацистов в Австрии; там, в уединении на вершине горы, у него возникли наброски многих идей параллельной обработки, включая языки программирования высокого уровня и «вычисляющие пространства» — т. е. клеточные автоматы. К.

               Цусе особенно интересовался численными моделями в механике, и физические мотивы играли основную роль в его работе. К несчастью, исторические обстоятельства воспрепятствовали более широкой известности его работ в то время.

              Работа фон Неймана по самовоспроизводящимся автоматам была завершена и описана А. Берксом, который сохранил активный интерес к этой области на протяжении нескольких последующих лет.

              Обратите внимание

              Его «Очерки по клеточным автоматам» являются хорошим введением в вопросы о клеточных автоматах, которые ставились в годы формирования вычислительных наук. В той же среде, т. е. в группе компьютерной логики Университета шт. Мичиган, Дж.

               Голланц приступил к использованию клеточных автоматов в задачах адаптации и оптимизации; был разработан программный имитатор универсальных клеточных автоматов общего назначения.

              https://www.youtube.com/watch?v=GsNA0edVtUc

              Тем временем профессиональные математики обратили внимание на итерационные преобразования, действующие на пространственно распределенные структуры с дискретным набором состояний — опять-таки клеточные автоматы! Недостаточность общения и единой терминологии вели к значительному дублированию работ.

              Игра Джона Конуэя «Жизнь», представленная широкой общественности ведущим рубрику математических игр и развлечений в журнале Scientific American М. Гарднером, некоторое время пользовалась популярностью, близкой к культу, и сделала выражение «клеточные автоматы» частью бытового жаргона целого поколения молодых ученых.

              Вопрос о том, могут ли клеточные автоматы моделировать непосредственно законы физики, а не только общие феноменологические аспекты нашего мира, был вновь поставлен Э.

               Фредкином, который проявлял активность и в более традиционных областях исследований клеточных автоматов, и Т. Тоффоли.

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

              Модели, которые явным образом сводят макроскопические явления к точно определенным микроскопическим процессам, представляют наибольший методологический интерес, потому что они обладают огромной убедительностью и ясностью.

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

              Важно

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

              Бурно развивающийся раздел теории динамических систем изучает возникновение хорошо описанных коллективных явлений — упорядочение, турбулентность, хаос, нарушение симметрии, фрактальность и др.

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

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

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

              Источник: http://life.written.ru/cellular_automata_review_by_toffoli

              Естественные алгоритмы: клеточные автоматы

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

              Пространство представлено равномерной сеткой, каждая ячейка или клетка которой содержит несколько битов данных; время идет вперед дискретными шагами, а законы мира выражаются единственным набором правил, скажем, небольшой справочной таблицей, по которой любая клетка на каждом шаге вычисляет своё новое состояние, основываясь на состоянияях её близких соседей. Таким образом, законы системы являются локальными и повсюду одинаковыми. «Локальными» в смысле того, что чтобы узнать, что произойдет мгновение спустя, достаточно посмотреть на состояние ближайшего окружения: никакое дальнодействие не допускается. «Одинаковость» означает, что законы везде одни и те же.

              Клеточные автоматы характеризуются двумя главными особенностями:

            1. n–мерная решетка, в которой каждая ячейка характеризуется дискретным состоянием в данный момент;
            2. динамическое поведение, контролируемое набором правил. Эти правила определяют положение ячеек в последующих поколениях, исходя из положения соседних ячеек.
            3. Ячейки в клеточном автомате запоминают положения автомата. Самый простой случай — это когда возможны только два состояния в ячейке: 0 — мертвая, или 1 — живая.

              Существует три типа соседства ячеек в клеточных автоматах (рассмотрим двумерные автоматы)

            4. Фон–Ньюманновское соседство, где каждая клетка имеет четырех соседей–ячеек — южную, северную, восточную и западную, а радиус соседства — 1:
            5. соседство Мура, где у каждой клетки восемь соседей по направлениям, радиусом 1:
            6. расширенное соседство Мура с радиусом 2 и больше
            7. В случаях одномерного автомата такие соседства будут отображаться только центральными строками.

              По своему поведению клеточные автоматы делятся на четыре класса. К первому классу относятся автоматы, приходящие через определенное время к устойчивому однородному состоянию. Автоматы второго класса через некоторое время после пуска генерируют стационарные или периодические во времени структуры.

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

              Такие автоматы являются кандидатами на прототип клеточной вычислительной машины.

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

              Совет

              Рассматривается бесконечная плоская решётка квадратных ячеек–клеток. Время в этой игре дискретно (t=0, 1, 2, …). Клетка может быть живой или мёртвой.

              Изменение её состояния в следующий момент времени t+1 определяется состоянием её соседей в момент времени t(соседей у клетки восемь, четверо имеют с ней общие рёбра, а четверо только вершины).

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

            8. Не должно быть ни одной исходной конфигурации, для которой существовало бы простое доказательство возможности неограниченного роста популяции.
            9. В то же время должны существовать такие начальные конфигурации, которые заведомо обладают способностью беспредельно развиваться.
            10. Должны существовать простые начальные конфигурации, которые в течение значительного промежутка времени растут, претерпевают различные изменения и заканчивают свою эволюцию одним из следующих трёх способов: полностью исчезают (либо из–за перенаселенности, то есть слишком большой плотности живых клеток, либо, наоборот, из–за разреженности клеток, образующих конфигурацию); переходят в устойчивую конфигурацию и перестают изменяться вообще или же, наконец, выходят на колебательный режим, то есть бесконечный цикл превращений с определенным периодом.
            11. Читайте также:  Ученые создали искусственный синапс, который способен автономно обучаться

              Следствием этих требований явились следующие правила игры «Жизнь»:

            12. Выживание. Каждая клетка, имеющая две или три соседние живые клетки, выживает и переходит в следующее поколение.
            13. Гибель. Каждая клетка, у которой больше трёх соседей, погибает из–за перенаселённости. Каждая клетка, вокруг которой свободны все соседние клетки или же занята всего одна клетка, погибает от одиночества.
            14. Рождение. Если число занятых клеток, с которыми граничит какая–нибудь пустая клетка в точности равно трём, то на этой клетке происходит рождение нового организма.
            15. пример работы клеточного автомата

              Источник: https://algorithmiccomposition.ru/article_entry_cellurar.html

              ПОИСК

                  Книга американских специалистов, излагающая теорию клеточных автоматов Дж. фон Неймана и описание машины клеточных автоматов на базе персональной ЭВМ (ШМ-РС). Такие машины могут использоваться для моделирования физических процессов, при решении комбинаторных и вычислительных задач, задач прикладной кибернетики.

              Изложение отличается простотой и ясностью и рассчитано на первоначальное ознакомление с предметом. [c.4]
                  Клеточные автоматы являются стилизованными, синтетическими мирами, определенными простыми правилами, подобными правилам настольной игры.

              Они имеют свой собственный вид материи, которая кружится в своих собственных пространстве и времени. Можно вообразить удивительное разнообразие этих миров. Можно действительно построить их и наблюдать, как они развиваются.

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

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

              7]

                  Машина клеточных автоматов является синтезатором миров. Подобно органу, она имеет клавиши и регистры, с помощью которых возможности инструмента можно приводить в действие, комбинировать и перекомпоновывать, а ее цветной экран является окном, через которое можно наблюдать мир, который сейчас играется . [c.7]

                  Итак, эта книга является вводным руководством по гармонии и оркестровке для композиторов миров на клеточном автомате. [c.7]

                  В этой книге мы исследуем выразительные возможности (в плане синтеза систем) конкретного набора средств, а именно законов, структур и явлений, поддерживаемых клеточными автоматами, с тем чтобы эти системы стали реально доступными для экспериментирования посредством использования машины клеточных автоматов с адекватными характеристиками. [c.8]

                  Данная глава является введением в клеточные автоматы и включает краткие исторические замечания и ссылки. [c.8]

              Обратите внимание

                  Клеточные автоматы являются дискретными динамическими системами, поведение которых полностью определяется в терминах локальных зависимостей, в значительной степени так же обстоит дело для большого класса непрерывных динамических систем, определенных уравнениями в частных производных. В этом смысле клеточные автоматы в информатике являются аналогом физического понятия поля . [c.8]

                  Как отмечено во введении, клеточный автомат может мыслиться как стилизованный мир.

              Пространство представлено равномерной сеткой, каждая ячейка которой, или клетка, содержит несколько битов данных время идет вперед дискретными шагами, а законы мира выражаются единственным набором правил, скажем небольшой справочной таблицей, по которой любая клетка на каждом шаге вычисляет свое новое со- [c.8]

                  Прежде чем поручать машине управлять миром на клеточном автомате, необходимо иметь ясное представление о том, как то же задание могло бы быть выполнено вручную. [c.9]

                  С другой стороны, структура клеточного автомата идеально пригодна для реализации на ЭВМ, обладающей высокой степенью параллелизма, локальными и единообразными взаимо- [c.11]

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

              2). Эти машины представляют собой лабораторные установки, в которых идеи, приведенные в этой книге, могут быть испытаны в конкретной форме и применены к синтезу огромного многообразия систем. [c.

              12]

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

              Важно

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

              Они стали темой или поводом бесчисленных диссертаций. О них много говорилось и писалось, но до последнего времени никто в действительности не видел большинство из них. [c.12]

                  Клеточные автоматы ввел в конце сороковых годов Дж. фон Нейман, следуя идее С. Улама [64 ], для того чтобы обеспечить более реалистические модели поведения сложных, пространственно протяженных систем [68] в клеточном авто- [c.12]

                  Тем временем профессиональные математики обратили внимание на итерационные преобразования, действующие на пространственно распределенные структуры с дискретным набором состояний [25], – опять-таки клеточные автоматы Недостаточность общения и единой терминологии вели к значительному дублированию работ. Важные характерные особенности клеточных автоматов, доказанные Ричардсоном [48 ] на [c.13]

                  Этот подход был использован для того, чтобы обеспечить предельно простые модели обычных дифференциальных уравнений физики, таких как уравнение теплопроводности, волновое уравнение [61] и уравнение Навье-Стокса [23, 18], которые могут мыслиться как предельные случаи исключительно простых процессов комбинаторной динамики. В частности, клеточные автоматы были созданы для того, чтобы дать точные модели динамики жидкостей, которые не только будят мысль, но и конкурентоспособны, по крайней мере в некоторых обстоятельствах, с точки зрения их вычислительной эффективности. [c.15]

                  В этой книге стандартная среда моделирования, которая будет постепенно вводиться, начиная с настоящей главы, представлена конкретной имеющейся в продаже машиной клеточных автоматов, а именно САМ-6. Основная причина этого выбора состоит в том, что аппаратные средства и программное обеспечение этой машины доступны в настоящее время широкому кругу пользователей. [c.16]

                  Однако, если вы хотите уметь добавлять новые элементы к своему набору миров, вам для описания правил клеточного автомата потребуется язык, удобный пользователю и понятный машине. Этот процесс создания правил формально вводится в гл. 4, а полностью разрабатывается в последующих главах. [c.20]

                  САМ-6 является машиной клеточных автоматов, предназначенной для того, чтобы служить лабораторией экспериментатора, средством сообщения результатов и средой для интерактивной демонстрации в режиме реального времени. [c.16]

              Совет

                  В машине клеточных автоматов текущий кадр, представленный содержимым всех плоскостей битов, во время цикла обновления заменяется новым согласно определенному рецепту. Результатом является один шаг эволюции конкретного клеточного автомата, а этот рецепт называется правилом этого клеточного автомата. [c.18]

                  При написании правила клеточного автомата мы определяем, как на каждую клетку повлияют некоторые соседние клетки.

              Точнее, мы определяем, как на каждый из четырех битов, составляющих клетку, повлияют несколько соседних битов некоторые из них могут располагаться на той же самой плоскости битов, а некоторые на остальных трех плоскостях. Насколько далеко может распространяться это влияние  [c.19]

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

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

              Выбор окрестности обсуждается в гл. 7. [c.19]

                  Кривые пространственные элементы. Мембраны, мицеллы, спирали.

              Более сложные высокоорганизованные структуры, получаемые изгибом низких структур Одно из многих квазиэквивалент-ных состояний метастабильная регистрация произвольной информации (учет пути) прогрессивное выделение и специализация информационной структуры Конечное число элементов Кластеры кристаллоиды Агрегирование путем включения других компонент ( кристалла-за -фермент). Информационноуправляемое агрегирование. Иерархическое агрегирование Иерархия уровней организации. Малая ширина каждого уровня Повторение по программе. Клеточные автоматы [c.434]

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

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

              Обратите внимание

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

              [c.5]

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

              Рецепт может относиться к окрестности с другой формой и размером, чем окрестность 3×3, и может включать чернила более чем одного цвета однако как число соседей, так и число цветов (т. е.

              число возможных состояний клетки) должны быть конечными, потому что мы хотим, чтобы обновление состояния клетки требовало конечного числа операций. [c.10]

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

                  В связи с этим обычные компьютеры здесь мало пригодны. Моделирование события в клеточном автомате может потребовать около тридцати мапшнных операций, содержащих каждая несколько машинных циклов, скажем 10 мс на быстродействующем компьютере. Для того чтобы вычислить 10 событий, при таком подходе потребовалось бы несколько лет  [c.11]

                  Термин не-фон-иеймаиовская архитектура часто используется для различения параллельных компьютеров этого вида и более привычных последовательных компьютеров. Необходимо, однако, заметить, что теория клеточных автоматов была введена самим фон Нейманом примерно в то же время, ко1да он работал над конструированием универсальных электронных компьютеров. [c.12]

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

              Важно

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

              13]

                  В конце войны, коща фон Нейман создавал один из первых электронных компьютеров, немецкий инженер К.

              Цусе прятался от нацистов в Австрии там, в уединении на вершине горы, у него возникли наброски многих идей параллельной обработки, включая языки программирования высокого уровня и вычисляющие пространства [76] – т. е. клеточные автоматы. К.

              Цусе особенно интересовался численными моделями в механике, и физические мотивы играли основную роль в его работе. К несчастью, исторические обстоятельства воспрепятствовали более широкой известности его работ в то время. [c.13]

                  Работа фон Неймана по самовоспроизводящимся автоматам была завершена и описана А. Берксом [68], который сохранил активный интерес к этой области на протяжении нескольких последующих лет.

              Его Очерки по клеточным автоматам [10] являются хорошим введением в вопросы о клеточных автоматах, которые ставились в годы формирования вычислительных наук. В той же среде, т. е. в группе компьютерной логики Университета шт. Мичиган, Дж.

              Голланд приступил к использованию клеточных автоматов в задачах адаптации и оптимизации [27 ] был разработан программный имитатор универсальных клеточных автоматов общего назначения. Месяцы работы с этим имитатором (см.

              [55]) убедили одного из авторов (Тоффоли) в необходимости более непосредственной и эффективной аппаратной реализации – машины клеточных автоматов. [c.13]

                  Игра Джона Конвея жизнь , представленная широкой общественности ведущим рубрику математических игр и развлечений в журнале Сайентифик Америкен М. Гарднером [20], некоторое время пользовалась популярностью, близкой к культу, и сделала выражение клеточные автоматы частью бытового жаргона целого поколения молодых ученых. [c.14]

              Совет

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

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

              В качестве введения в эти области и руководства к машинам, разработанным для этих более специализированных приложений, может быть использована книга Престона и Даффа Современные клеточные автоматы [46 ]. [c.14]

                  Вопрос о том, могут ли клеточные автоматы моделировать непосредственно законы физики, а не только общие феноменологические аспекты нашего мира, был вновь поставлен Э. Фредкином, который проявлял активность и в более традиционных областях исследований клеточных автоматов (см.

              [3]), и Т. Тоффоли [55]. Основной целью настоящего исследования является рмулировка компьютероподобных моделей в физике, сохраняющих информацию, а значит и одно из наиболее фундаментальных свойств микроскопической физики, а именно обратимость [17, 58, 35]. [c.

              14]

                  Бурно развивающийся раздел теории динамических систем изучает возникновение хорошо описанных коллективных явлений – упорядочение, турбулентность, хаос, нарушение симметрии, фрактальность и др.

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

              Клеточные автоматы обеспечивают богатую и непрерывно растущую коллекцию типичных моделей, в которых эти явления могут быть изучены относительно легко [66, 15, 5]. Систематическое использование клеточных автоматов в этом контексте энергично проводилось С.

              Вольфрамом [70-73, 43] его сборник статей по теории и применениям клеточных автоматов [74] содержит обширную библиографию. [c.15]

              Обратите внимание

                  Итак, клеточные автоматы, по-видимому, нашли устойчивое (и все более важное) применение в качестве концептуальных и практических моделей пространственнораспределенных динамических систем, для которых физические системы являются первыми и наиболее важными прототипами. [c.15]

                  Физически САМ-6 состоит из модуля, который вставляется в один разъем IBM-P (XT, АТ или совместимых с ними моделей), и управляющего программного обеспечения, работающего в среде P -D0S2.

              В то время как этот легко доступный головной компьютер обеспечивает размещение, экранирование, электропитание, дисковую память, монитор и стандартную операционную среду, вся действительная работа по моделированию клеточных автоматов с очень высокой скоростью совершается самим модулем с быстродействием, сравнимым (для этого частного приложения) с быстродействием RAY-1. [c.17]

                  Несколько модулей САМ могут быть объединены так, чтобы получить больший клеточный автомат. В этом случае склеивание краев соответствующим образом модифищ1руется, так что обертывание правильно применяется и к большему листу. [c.19]

              Источник: http://chem21.info/info/1877598/

              Клеточные автоматы (из вики)

              ИСТОРИЯ

              Станислав Улам, работая в Лос-Аламосской национальной лаборатории в 1930-е годы, изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота.

              В 1970-е получила известность двухмерная клеточно-автоматная модель с двумя состояниями, известная как игра «Жизнь».

              Изобретенная Джоном Конвеем и популяризованная Мартином Гарднером, она использует следующие правила: если клетка имеет двух «живых» соседей, она остаётся в прежнем состоянии.

              Если клетка имеет трёх «живых» соседей, она переходит в «живое» состояние. В остальных случаях клетка «умирает».

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

              В 1969 году немецкий инженер Конрад Цузе опубликовал книгу «Вычислимый космос», где выдвинул предположение, что физические законы дискретны по своей природе, и что вся Вселенная является гигантским клеточным автоматом. Это была первая книга из области, называемой сейчас цифровой физикой.

              Клеточные автоматы в естественной среде

              Некоторые живые организмы проявляют свойства клеточных автоматов. Раскраска раковин ряда морских моллюсков, например, родов Conus или Cymbiola, генерируется естественным одномерным клеточным автоматом, результат эволюции которого похож на Правило 30.

              Их пигментные клетки располагаются тонкой полоской вдоль края раковины. Секреция пигмента каждой клетки зависит от активирующей и ингибиторной активности соседних клеток. В процессе роста раковины полоса клеток формирует цветной узор на её поверхности.

              Растения регулируют приток и отток газообразных веществ посредством механизма клеточных автоматов. Каждое устьице на поверхности листа действует как ячейка[источник не указан 277 дней].

              Нейронные сети также могут быть использованы как клеточные автоматы. Сложный движущийся узор на коже головоногих является отражением паттернов активирования в мозгу животных.

              Классификация

              Классификация по типам поведения

              Правило 40(Класс 1) со случайными начальными условиями. Как видно, информация быстро исчезает в этой системе.

              Правило 3(Класс 2) со случайными начальными условиями. Очевидно появление периодических структур

              Правило 18(Класс 3) со случайными начальными условиями. Видно, что начальные условия порождают хаотические движения внутри системы.

              Важно

              Правило 193(Класс 4) со случайными начальными условиями. Можно увидеть порождение устойчивых структур(колонка белых треугольников и взаимодействие таких структур в других частях изображения.)

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

              • Класс 1: Результатом эволюции почти всех начальных условий является быстрая стабилизация состояния и его гомогенность. Любые случайные конструкции в таких правилах быстро исчезают.
              • Класс 2: Результатом эволюции почти всех начальных условий является быстрая стабилизация состояния, либо возникновение колебаний. Большинство случайных структур в начальных условиях быстро исчезает, но некоторые остаются. Локальные изменения в начальных условиях оказывают локальный характер на дальнейший ход эволюции системы.
              • Класс 3: Результатом эволюции почти всех начальных условий являются псевдо-случайные, хаотические последовательности. Любые стабильные структуры, которые возникают почти сразу же уничтожаются окружающим их шумом. Локальные изменения в начальных условиях оказывают широкое, неопределямое влияние на ход всей эволюции системы.
              • Класс 4: Результатом эволюции почти всех правил являются структуры, которые взаимодействуют сложным и интересным образом с формированием локальных, устойчивых структур, которые способны выживать длительное время. В результате эволюции правил этого класса могут получаться некоторые последовательности Класса 2, описанного выше. Локальные изменения в начальных условиях оказывают широкое, неопределямое влияние на ход всей эволюции системы. Некоторые клеточные автоматы этого класса обладают свойством универсальности по Тьюрингу. Последний факт был доказан для Правила 110 и игры «Жизнь».

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

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

              Оригинальный текст  (англ.)  

              Тоталистичные клеточные автоматы

              Существует специальный класс клеточный автоматов, называемых тоталистичными.

              На каждом шаге эволюции клеточного автомата значение ячейки равно какому-либо целому числу(обычно выбираемого из конечного множества), а новое состояние клетки определяется суммой значений клеток-соседей и, возможно, предыдущим состоянием клетки.

              Если состояние клетки на новом шаге зависит от её предыдущего состояния, то такой клеточный автомат называется внешним тоталистичным. Игра Жизнь является примером внешнего тоталистического клеточного автомата с набором значений ячеек .

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

              Связанные определения клеточных автоматов

              Существует множество возможных обобщений концепций клеточных автоматов.

              Клеточный автомат работающий на сетке, компонентами которой являются шестиугольники, а не квадраты(правило 34/2)

              Один из них — использование сетки не с квадратами(гиперкубами в многомерном случае), а с другими геометрическими фигурами в её основе. Например, если поле представлено шестиугольным паркетом, то шестиугольники будут клетками.

              Однако иногда такие клеточные автоматы оказывались идентичными клеточным автоматам на сетке с квадратными клетками, только при этом было необходимо вместе специальные правила отношений с клетками-соседями.

              Другой способ обобщения — использование нерегулярной сетки(например, в виде Мозаики Пенроуза).

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

              Или, например, в игре «Жизнь» добавляется правило, что клетка с определенной вероятностью может изменить свой цвет на противоположный, а другие правила этого клеточного автомата остаются без изменений.

              Определение соседства клетки может меняться с течением времени иили пространства. Например, на первом шаге соседями будут горизонтально смежные клетки, а на другом — вертикально смежные.

              Совет

              В клеточных автоматах на новое состояние клетки не влияют новые состояния смежных клеток. Правило можно поменять: можно сделать так, что, например, в блоках 2 на 2 состояния клеток зависят от состояния клеток внутри блока и от таких-же смежных блоков.

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

              Свойство обратимости

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

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

              Конфигурации, не имеющие предшествующих, то есть недостижимые в данном клеточном автомате, носят название «Сады Эдема».

              Для одномерных клеточных автоматов существуют алгоритмы определения обратимости или необратимости. Однако для клеточных автоматов с двумя и более измерениями таких алгоритмов нет.

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

              Такие системы изучались Томасо Тоффоли (Tommaso Toffoli) и Норманом Марголусом (Norman Margolus). Существует несколько типов обратимых конечных автоматов. Наиболее известными являются клеточный автомат второго порядка и блочный клеточный автомат.

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

              Обратите внимание

              Также, было доказано, что любой обратимый клеточный автомат может быть сэмулирован блочным клеточным автоматом.

              Компьютерное моделирование реакции Белоусова — Жаботинского в тонком слое жидкости в чашке Петри.

              Реакция Белоусова — Жаботинского представляет собой пространственно-временной химический осциллятор, который может быть смоделирован клеточным автоматом. В 1950-х годах А. М.

               Жаботинский, продолжая работу Б. П.

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

              Источник: http://ielf.ucoz.ru/blog/kletochnye_avtomaty_iz_viki/2014-06-11-591

              Ссылка на основную публикацию
              Adblock
              detector