Не похожие на «жизнь» клеточные автоматы

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

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

Еще в 1970 году А.Н. Колмогоровым давался прогноз, что с “развитием современной вычислительной техники будет во многих случаях разумно изучение реальных явлений вести, избегая промежуточный этап их стилизации в духе математики бесконечного и непрерывного, переходя прямо к дискретным моделям”.

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

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

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

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

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

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

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

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

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

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

Важно

Жизнь, как естественный процесс – явление настолько сложное и увлекательное, что тысячи ученых пытались раскрыть ее тайны.

Свой вклад в решение этой проблемы внес и человек, не имевший к биологии никакого отношения, английский математик Джон Хортон Конвей.

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

Действие игры происходит на плоскости, разделенной на клетки. Каждая клетка окружена 8 такими же клетками (так называемая окрестность Мура) и может находиться в двух состояниях – живом или мертвом (быть пустой).

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

Во времени эти состояния дискретно изменяются в соответствии со следующими правилами (генетическими законами Конвея).

  1. Выживание или гибель. Если живая клетка имеет менее 2 или более 3 соседей в окрестности из 8 клеток, то в следующем поколении она умирает (моделирование реальных условий – недостатка питания или перенаселенности), в противном случае она выживает.
  2. Рождение. В пустой клетке появляется новая живая клетка, если у нее ровно 3 соседа.

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

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

Познать “Жизнь” на практике проще всего с помощью листа бумаги в клеточку и ручки. Можно воспользоваться также шахматной доской и обычными шашками двух цветов. Еще проще – использовать для этой цели компьютер. Уже на заре развития компьютерной техники были написаны многочисленные программы, моделирующие “Жизнь”.

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

Планер (glider) – это самый ранний из обнаруженных и наиболее примечательный объект, одной из особенностей которого является его способность спонтанно возникать в совершенно произвольных ситуациях и перемещаться за пределы видимого пространства (в случае, когда движение направлено в противоположную сторону от сосредоточения основных объектов популяции). Через определенное количество шагов планеры покидают пределы освоенной области и устремляются в “космические дали”.

Совет

Более подробную информацию о игре “Жизнь” и программы для наблюдения за эволюцией объектов можно найти по следующему URL: elvisti.kiev.ua/skl/conwey1/w_life_n.htm.

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

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

Представим себе некую исходную фигуру на плоскости, к которой начинают применяться правила “Жизни”.

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

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

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

Задания

1. Постройте модель процесса распространения инфекции стригущего лишая по участку кожи размером n x n (n-нечетное) клеток. Заражение начинается с центральной клетки.

В каждый интервал времени пораженная инфекцией клетка может с вероятностью 1/2 заразить любую из соседних здоровых клеток. Через шесть единиц времени зараженная клетка становится невосприимчивой к инфекции.

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

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

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

2. Разработайте имитационную модель системы “хищник-жертва” по следующей схеме. Остров размером 20×20 заселен дикими кроликами, волками и волчицами. Имеется несколько представителей каждого вида.

Кролики довольно глупы: в каждый момент времени они с одинаковой вероятностью 1/9 передвигаются в один из восьми соседних квадратов (за исключением участков, ограниченных береговой линией) или просто сидят неподвижно. Каждый кролик с вероятностью 0,2 превращается в 2 кроликов.

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

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

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

Источник: http://www.linuxcookbook.ru/books/informatika1/ch_09_modell/01_model/02_life/index.html

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

?evan_gcrm (evan_gcrm) wrote,
2017-06-15 00:18:00evan_gcrm
evan_gcrm
2017-06-15 00:18:00Categories:

  • наука
  • it
  • технологии

Оригинал взят у lexpartizan

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

И по которым они изменяются с каждым циклом.

Например, у нас есть громадное поле клеток и несколько простых правил:

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

2. Если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить;
3. В противном случае, если соседей меньше двух или больше трёх, клетка умирает («от одиночества» или «от перенаселённости»).Эти правила придумал математик Джон Конвей в 1970 году и назвал их игрой “жизнь”. Это наиболее известный пример клеточного автомата. Дело в том, что несмотря на простейшие правила, лежащие в основе, игра жизнь неожиданно смогла воспроизвести и поддерживать очень сложные структуры. Всего 2-3 правила, а там есть чрезвычайно сложное поведение некоторых структур. Есть стабильные фигуры, есть динамические фигуры (глайдеры, которые повторяют форму через несколько итераций, но смещаются), есть фигуры, порождающие эти глайдеры, есть фигуры, принимающие глайдеры и порождающие столько же глайдеров, сколько приняли. Есть много чего. Настолько много, что в этой игре удалось реализовать “машину Тьюринга”.

Поль Рендель 2 апреля 2000 года создал модель машины Тьюринга с помощью клеточного автомата Джона Хортона Конвея, а 10 февраля 2010 года повторил свой замечательный опыт. В первой модели использовалась решетка 1714 х 1647, с помощью конечных автоматов которой была создана машина Тьюринга.

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

Существуют и другие успешные примеры создания машин Тьюринга с помощью игры «Жизнь», некоторые из них даже получили собственные названия: MRM (Minsky Register Machine) или ее универсальная версия URM, а также CoreWorld, LogiCell и другие.

То есть вычислительное устройство, способное к любым вычислениям.А это означает, что на такой машине можно сделать что? Правильно, запустить игру “жизнь”.

Важно

Жители виртуальной Вселенной игры “Жизнь” могли бы создать собственную виртуальную реальность! В которой могли бы изменить правила и клетки бы не умирали))Конечно, правила для игры “жизнь” могут быть и другими и это будет уже другой клеточный автомат.

Как задать правила? Да теми же таблицами!

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

Сколько значений надо заполнить?

2 в 9 степени = 512. 3Х3 клетки могут принять 512 значений и каждому из этих значений нужно поставить результат. То есть какой цвет примет клетка для каждого значения. А вот комбинаций таких результатов уже будет 2 в степени 512. В общем, больше атомов во Вселенной. И у каждого будет своё поведение (не факт, что интересное). И это только для одного плоского клеточного автомата 3Х3.А ведь можно взять другую окрестность точек, например, не 8 точек вокруг, а 4 точки по каждой стороне, проигнорировав диагональные. Или считать не только ближайшие точки, но и точки за ними, то есть не квадрат 3Х3, а квадрат 5Х5. Или ввести третье измерение. А ещё можно для этих правил ввести вероятность, сделав их вероятностными, когда клетка имеет шанс жить вопреки. Или двигаться в случайную сторону. Например, это имеет место для модели диффузии.Простой клеточный автомат с правилами (движемся хаотично, при столкновении меняемся местами) даёт вполне себе реалистичную картину диффузии.Чуть хитрее поведение газов. Ещё хитрее – поведение жидкости в полном соответствии с системой дифференциальных уравнений Навье-Стокса, которые довольно трудно считаются в лоб, легко симулируются практически с абсолютной точностью простым (но довольно большим по размеру) клеточным автоматом.Так что клеточные автоматы применяются в газо и гидродинамике. А также в оптике. По весьма схожим правилам.

А также в физике при моделировании столкновений элементарных частиц, в квантовой физике, даже в теории световых полей.

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

И ещё много где применяются.

При моделировании социальных процессов (вообще схожих с гидродинамикой). Например, распространение информации в соцсетях можно промоделировать.

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

Читайте также:  В армию сша будут поставлены роботы-спасатели на общую сумму в 20,6 млн долларов

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

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

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

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

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

Однако многие учёные считали, да и сейчас считают, что мозг близок к клеточному автомату.

Ведь и правда, если представить каждую клетку, как нейрон…

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

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

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

Например, есть так называемые L-системы.

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

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

Сейчас L-системы применяются для процедурной генерации растений для 3D-пакетов и игр.

И для создания гипножаб:

Принцип один: Простые правила – сложное поведение.

Всё это не могло не натолкнуть учёных на мысль:

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

Это была первая книга из области, называемой сейчас цифровой физикой.

Что если вся наша Вселенная – громадный клеточный автомат? И кажется такой сложной (ньютонова физика, противоречащие друг другу ОТО, СТО и квантовая физика), но на самом деле где-то глубоко внутри, подчиняется простейшим правилам.

Совет

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

Эту теорию продолжает развивать расовый жид Стивен Вольфрам, выпустивший книгу “New kind of science”. Вольфрам нашел способ из графов и комбинаторики создавать такие сети, которые могли бы соответствовать нашему пространству-времени, гравитации и прочим законам. Это клеточный автомат, но не из цифр и не из клеток.

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

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

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

Часто просто наблюдают за поведением при случайных правилах. А область правил просто невероятно огромна даже для модели игры “Жизнь”(область определения 3Х3 клетки, плоскость). Так что Вольфраму будет нелегко.

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

А теперь натянем сову на глобус.

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

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

Ведь матрица – основа клеточного автомата.

Картинка кликабельна.

Источник: https://evan-gcrm.livejournal.com/978425.html

Клеточные автоматы (обзор Гарднера)

Книга Мартина Гарднера «Математические досуги» вышла в 1972 году. Её последняя глава посвящена игре «Жизнь», в которой также есть небольшой обзор теории клеточных автоматов. Многие сведения уже устарели.

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

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

Игра Конуэя «Жизнь» вызвала огромный интерес у ученых, занимающихся разработкой проблем, связанных с использованием компьютеров. Поэтому остановимся на некоторых основных фактах развития «теории клеточных автоматов» — области науки, занимающейся изучением игр, аналогичных конуэевской «Жизни».

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

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

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

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

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

На состояние любой клетки оказывает влияние конечное число соседних клеток. Во времени состояния пространства изменяются дискретно, в соответствии с «правилами перехода», которые необходимо применять одновременно ко всем клеткам.

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

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

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

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

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

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

Важно

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

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

В этой системе ячейки могут находиться лишь в двух состояниях, каждая из них, как и в примере фон Неймана, имеет четырёх соседей, а правила перехода сводятся к следующим. Каждая клетка, имеющая в момент времени t четное число (0, 2, 4, …

) живых соседей, в момент времени t + 1 становится пустой (то есть переходит в нулевое состояние или, если она уже находилась в нулевом состоянии, остаётся в нём). Каждая клетка, имеющая в момент времени t нечетное число (1, 3, …

) соседей, в момент времени t + 1 становится живой (то есть переходит в ненулевое состояние или сохраняет его, если она уже в нём находилась).

Через 2n ходов (число n зависит от выбора конфигурации) любая конфигурация живых клеток в таком пространстве воспроизведет себя четыре раза: одна копия расположится справа, другая — слева, третья — сверху, четвёртая — снизу от того (уже пустого) места, где находилась начальная конфигурация.

Новая конфигурация через 2n шагов снова размножится (с коэффициентом воспроизводства, равным 4) и т. д. Число копий увеличивается в  геометрической прогрессии 1, 4, 16, 64… На рисунке показаны полтора цикла размножения тримино в форме прямого угла.

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

Множество автоматов такого рода, отличающихся друг от друга схемой примыкания соседних клеток, числом состояний и правилами перехода, исследовал С. Улам. В опубликованной им (совместно с Робертом Г. Шрандтом) в 1967 году статье «О рекурсивно определённых геометрических объектах и схемах роста» Улам описал несколько игр.

На рисунке показано сорок пятое поколение организма, родившегося из одной-единственной фишки, стоявшей в центральной клетке.

Как и в игре Конуэя, клетки в игре Улама могут находиться в двух состояниях, но соседними считаются клетки, примыкающие к данной лишь по вертикали, но не по диагонали («соседи» в смысле фон Неймана).

Рождение фишки происходит на клетке, имеющей одного и только одного соседа, а все клетки поколения n погибают после рождения поколения n + 2. Иначе говоря, на любом этапе эволюции выживают лишь два последних поколения. На рисунке черными изображены новорожденные клетки (их 444).

Совет

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

В следующей за столкновением «битве» одной стороне иногда удавалось одержать верх над другой, а иногда обе армии исчезали. Улам рассмотрел также игры на трёхмерных досках — кубических «паркетах», заполняющих всё пространство. Основные результаты Улама собраны в его статьях, опубликованных в сборнике «Очерки теории клеточных автоматов» (Essays on Cellular Automata, University of Illinois Press, 1970, ed. by Arthur W. Burks).

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

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

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

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

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

«Сады Эдема» должны быть заданы с самого начала — в нулевом поколении. Поскольку конфигурации такого типа не имеют «предшественников», они не могут быть самовоспроизводящимися. Подробно метод Мура изложен в его популярной статье «Математика в биологических науках» (Scintific American, сентябрь 1964).

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

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

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

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

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

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

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

Читайте также:  Мнение: самоуправляемые авто будут популярнее любого общественного транспорта

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

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

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

Увлекательная жизнь клеточных автоматов, или Как в «Жизни» «Тетрис» запустили

sentinel@home: Полный список публикаций | Форум | Linux.su

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

Однако при ближайшем рассмотрении вся история оказывается не только ещё более сложной, но и чертовски интересной, и очень важной в смысле перспектив.

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

Важно

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

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

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

Напоминает биологию, правда? Отсюда и название.

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

Игра «Жизнь» в программе Golly — одном из лучших симуляторов клеточных автоматов (см. далее).

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

Сегодня, конечно, нет необходимости мучиться с доской и фишками — проще и правильней воспользоваться соответствующими программами, коих написано несчётное множество («Жизнь» очень просто запрограммировать, почему она и входит в число излюбленных игр, на которых программированию учатся и даже соревнуются).

Совет

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

Задаёте исходную конфигурацию, нажимаете «Пуск» и на экране начинается волшебство: клетки, словно микробы, делятся и умирают, сражаются, образуют причудливые формации… Наблюдать за процессом увлекательно, даже забавно, но на самом деле это было придумано не только забавы для.

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

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

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

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

Заслуга же Конвея как раз в том, что он искал и нашёл один из, вероятно, простейших клеточных автоматов, обладающих тем же свойством, что и прототип: правила «Жизни» обладают тьюринговой полнотой, что, попросту говоря, означает, что на игровом поле «Жизни», вот из этих самых простейших клеток, можно построить сколь угодно сложные логические структуры. Хоть электронные часы, хоть настоящий компьютер! Правда, оговорюсь, в теории. С практикой сложнее.

С тех самых пор, как Конвей опубликовал свою историческую статью в научно-популярном журнале, «Жизнь» и клеточные автоматы стали весьма популярной темой. Задача создания или открытия всё более и более сложных структур терзает миллионы любителей головоломок! Вот только вручную играть в такие игры непросто.

Поэтому почти сразу после публикации Конвея, «Жизнь» запрограммировали на тогдашних вычислительных машинах (первой, говорят, была PDP-7, стоимостью в полмиллиона долларов в сегодняшнем эквиваленте: ну не изобрели ещё тогда персоналку!).

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

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

Глайдер: одна из самых простых полезных структур в «Жизни». Если вы повторите этот рисунок на игровом поле «Жизни», он поведёт себя точно таким же образом.

Так и были открыты первые многоклеточные структуры, обладающие необычными свойствами. Например, знаменитый «Глайдер» — который словно бы летит по игровому полю («Глайдер» стал легендарным и впоследствии предложен на роль символа хакерского движения). Или «Галактика Кока»: чуть более сложное образование, напоминающее вращающуюся звёздную спираль с астрономических снимков.

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

Всю летопись сегодня можно посмотреть, например, в открытой веб-энциклопедии по игре «Жизнь» (да, такая существует — и продолжает писаться!): по ней ясно видно, как с каждым годом сложность открытий росла, достигнув к концу нулевых невероятных величин.

Вот, например, структура, названная «кораблём Gemini»: она занимает площадь в 4 миллиона на 4 миллиона клеток и живёт циклами по 34 миллиона ходов! Вообразите объём вычислений, необходимых для расчёта эволюции такого образования!

Или вот другая примечательная структура: открытый в 2005-м «Метапиксель OTCA». Это образование размером 2058 на 2058 клеток, живущее циклами по (примерно) 35 тысяч ходов. Но именно оно оказалось очень важным для «Жизни» в целом.

Дело в том, что «Метапиксель» способен имитировать одиночную клетку из «Жизни»: если расставить бок о бок несколько таких структур, можно сыграть ими в «Жизнь»! Попросту говоря, круг замкнулся: в игре создано образование, способное имитировать саму игру.

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

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

Важно

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

Таким образом, к примеру, на поле «Жизни» были построены уже упоминавшиеся часы с цифровой индикацией.

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

История этой задачки начинается 4 года назад, когда на популярном сайте головоломок для программистов кто-то предложил: поскольку «Жизнь» тьюринг-полная, то есть теоретически в ней можно создать что угодно, пусть кто-нибудь построит там «Тетрис»! Три года задача оставалась без ответа, а потом вокруг неё начал подбираться коллектив энтузиастов — и, потратив больше года на решение, они таки её решили.

За основу ребята взяли уже знакомый вам «Метапиксель OTCA». Он стал своеобразным кирпичиком, с помощью которого были созданы аналоги проводов (по которым бегут биты) и логических элементов (из которых построен любой настоящий компьютер).

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

Язык процессора они назвали ассемблером QFTASM, но чтобы проще было программировать, написали и более высокоуровневый язык COGOL. И вот на нём уже и запрограммировали «Тетрис».

Это один из ключевых блоков: процессор. Каждая клетка здесь — Метапиксель OTCA.

Запустить результат сегодня можно прямо в браузере (щёлкните там кнопку Run). Но теперь, зная, как это построено, вы в силах оценить и истинную сложность проекта.

Построенный ребятами компьютер имеет размер 1436х5082 клеток, каждая из которых это «Метапиксель OTCA».

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

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

Совет

Однако исследования клеточных автоматов продолжаются — и «Жизни» в том числе. Энтузиастам по-прежнему удаётся открывать случайно или конструировать сложные структуры, обладающие необычными свойствами. При этом, бывает, они получают имена в честь создателей. Так что реально есть возможность вписать своё имя в историю.

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

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

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

Поэтому не исключено, что следующей большой вехой станет воссоздание в «Жизни», например, простейшего червя — помните, над которым уже бьются программеры? А как вам задача перехитрить творца? Или сформулировать наконец критерий живого вообще? То ли ещё будет!

P.S. Отличная подборка исходников, реализующих «Жизнь» на разных языках программирования, есть в проекте Rosetta Code.

клеточный_автомат,Жизнь,Тетрис,игра,симуляция,цифра,жизнь,Джон_Конвей,Джон_фон_Нейман,машина_Тьюринга,проблема_останова

Источник: http://knoppix.ru/sentinel/021017.html

Клеточные автоматы – реализация и эксперименты

13.08.2003 Автор: Лев Наумов, Анатолий Шалыто

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

Один из крупнейших специалистов в области информатики — Марвин Минский [1] считает, что самым важным при этом, видимо, является изучение различных путей возникновения сложного поведения при использовании простых устройств, действий, описаний или концепций.

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

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

В последние десятилетия проводился ряд исследований, посвященных анализу динамических систем. К этой области, в частности, относится теория самовоспроизводящихся структур [2].

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

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

К рассматриваемой области принадлежит также теория хаоса [4], признанная, наряду с теорией относительности и квантовой теорией [5], одним из основных теоретических достижений XX в. Нельзя сказать, что математический аппарат, применяемый в ней, прост. И для этой теории весьма актуальны исследования клеточных автоматов.

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

Рассматриваются два класса клеток: с памятью, обладающие лишь двумя состояниями, и без памяти.

Читайте также:  Инвестиции евросоюза в робототехнику. 2,8 млрд. долларов были инвестированы в проект sparc

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

Клеточные автоматы были предложены в работе фон Неймана [6]. Большой интерес к ним вызван тем, что такие автоматы являются универсальной моделью параллельных вычислений подобно тому, как машины Тьюринга являются универсальной моделью для последовательных вычислений [7].

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

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

В общем случае клеточные автоматы обладают следующими свойствами.

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

Клеточные автоматы можно реализовать разными способами. В данной работе применен такой подход.

  1. Вводятся два массива для хранения состояний клеток: первый из них содержит текущее состояние каждой клетки, второй предназначен для хранения нового ее состояния.
  2. Определяется функция переходов клетки решетки. Для выявления следующего ее состояния в качестве параметров в функцию переходов передаются текущие значения состояний клеток окрестности, возможно, включая ее саму. Эта функция будет задана в виде булевой формулы.
  3. На нулевом шаге решетка (первый массив) заполняется начальными данными, что полностью определяет поведение системы для выбранных решетки и функции переходов клетки.
  4. вычисления новых состояний вводится цикл. На каждой итерации для любой клетки, используя в качестве переменных элементы первого массива, определяется ее новое состояние, помещаемое во второй массив. Значения аргументов функции переходов берутся из первого массива.
  5. По завершении итерации значения из всех элементов второго массива переносятся в первый, что обеспечивает синхронное изменение значений состояний всех клеток решетки.
  6. Визуализируется содержимое решетки. В зависимости от ее размерности (одномерная или двумерная) отображение решетки производится по-разному.6.1. Для одномерной (линейной) решетки после каждой итерации выводится соответствующая ей строка. Их расположение одна под другой позволяет наблюдать динамику системы во времени (ось времени направлена вертикально вниз).

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

  7. Нажатием клавиши выполняется переход к пункту 4, а нажатие на клавишу q завершает работу программы.

Чтобы облегчить понимание листингов программ, в них применяется текстовый вывод информации. Программы, использованные в примерах, можно найти на сайте http://is.ifmo.ru в разделе «Статьи».

Одномерные клеточные автоматы

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

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)-й клетки в данный момент времени.

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

Пример 1. Пусть функция переходов клетки имеет такой вид:

y'[i] = y[i-1] | y[i] | y[i+1],

где | — символ логической операции «дизъюнкция» на языке программирования Си.

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

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

Важно

Эта программа позволяет представить поведение клеточного автомата во времени (рис. 1). Такое поведение может быть названо «пирамида».

Пример 2. Если при сохранении функции переходов в начальном заполнении решетки изменить состояние еще одной клетки с нуля на единицу, то поведение автомата станет другим (рис. 2). Оно может быть названо «горы».

Пример 3. Второй клеточный автомат характеризуется следующей функцией переходов:

y'[i] = y[i-1] | y[i] ^ y[i+1],

где ^ — символ логической операции «неравнозначность» («сумма по модулю два») в языке программирования Си.

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

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

y'[i] = y[i-1] ^ y[i] ^ y[i+1].

Этот автомат при тех же начальных условиях, что и в предыдущем примере, порождает самовоспроизводящуюся структуру (рис. 4).

Двумерные клеточные автоматы

Окрестность из восьми клеток

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

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]).

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

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

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

Программа, реализующая игру «Жизнь», структура которой была описана выше, приведена в листинге 2. В ней решетка имеет размеры 23х23, а в качестве начальных условий выбран «планер» [9].

«Планер» был выбран в качества примера, так как является наиболее простым из «летающих» объектов. Он «летает» в том смысле, что перемещается за счет самовоспроизведения, происходящего с периодом в четыре шага.

Пример 6. В качестве примера самовоспроизведения рассмотрим клеточный автомат, функционирующий по правилу:

y'[i][j] = 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].

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

На рис. 5 приведена начальная конфигурация решетки, а на рис. 6 — результат ее самовоспроизведения через восемь шагов.

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

T = 2 [log2(max(a;b))] ,

где a и b — ширина и высота «зародыша» соответственно.

Для начальной конфигурации, изображенной на рис. 5, a = 3, b = 5. Поэтому T = 8, и следовательно, самовоспроизведение имеет место через 8, 16, 32, 64 и т. д. шагов.

Окрестность из четырех клеток

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

Рассмотрим в качестве окрестности данной клетки лишь те, которые имеют общую сторону с ней и называются «главными соседями».

Пример 7. Для иллюстрации самовоспроизведения при помощи автомата с такой окрестностью выберем следующую функцию переходов:

y'[i][j] = y[i][j] ^ y[i-1][j] ^ y[i][j+1] ^

^ y[i+1][j] ^ y[i][j-1].

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

Ta = 2 [log2 a] и Tb = 2 [log2 b] .

При этом период полного самовоспроизведения вычисляется на основе соотношения:

T = max(Ta ; Tb) .

Совет

Для рассматриваемого «зародыша» (рис. 5) период самовоспроизведения по горизонтали Ta равен 4 (рис. 7), а по вертикали, Tb равен 8 (рис. 8). Поэтому полный период самовоспроизведения T равен 8.

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

Пример 8. Если сохранить функцию переходов и выбрать в качестве начальной конфигурации единицу в центральной точке решетки, то на 15-м шаге получится конфигурация, изображенная на рис. 9, а на 29-м — на рис. 10.

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

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

Это объясняется тем, что информация распространяется за шаг на одну клетку, и поэтому из центральной она дойдет до границы за (23-1)/2 шагов.

Автоматы с клетками без памяти

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

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

Такой класс назовем «автоматами с клетками без памяти».

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

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

y'[i] = y[i-1] ^ y[i+1].

Поведение этого автомата во времени показано на рис. 11.

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

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

y'[i][j] = y[i-1][j] ^ y[i][j+1] ^

^ y[i+1][j] ^ y[i][j-1],

приведена в работе [10].

Искусственная жизнь

Сейчас на смену термину «искусственный интеллект» пришел более широкий термин — «искусственный интеллект и искусственная жизнь» [11]. По мнению авторов, настоящую работу можно рассматривать как введение в «искусственную жизнь». Кроме того, отметим, что активно развивается такая наука, как синергетика.

Ее название происходит от греческих слов «син» — совместный и «эргос» — действовать [12]. Поэтому синергетика — это наука о совместном согласованном поведении многих элементов как единого целого в составе сложной системы.

Из изложенного следует, что данная работа может рассматриваться также и в качестве введения в «синергетику».

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

Работа выполнена при поддержке Российского фонда фундаментальных исследований по гранту №02-07-90114 «Разработка технологий автоматного программирования»

Литература

  1. Минский М. Вычисления и автоматы. М.: Мир, 1971.
  2. Пайтген Х.О., Рихтер П.Х. Красота фракталов. Образы комплексных динамических систем. М.: Мир, 1993.
  3. Вирт Н. Алгоритмы и структуры данных. СПб.: Невский диалект, 2001.
  4. Пригожин И., Стенгерс И. Порядок из хаоса. Новый диалог человека с природой. М.

    : Эдиториал УРСС, 2000.

  5. Пайс А. Гении науки. М.: Институт компьютерных исследований, 2002.
  6. Нейман Дж фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971.
  7. Шалыто А., Туккель Н. От тьюрингова программирования к автоматному // Мир ПК. 2002. №2.
  8. Варшавский В.И., Мараховский В.Б., Песчанский В.А., Розенблюм Л.

    Я. Однородные структуры. М., 1973.

  9. Гарднер М. Математические досуги. М.: Мир, 1972.
  10. Федотьев А. Клеточный автомат -.
  11. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. М.: Эдиториал УРСС, 2002.
  12. Колесников А.А. Шанс для рывка // Поиск. 2002. №42.

Об авторах

Наумов Лев Александрович — студент кафедры «Компьютерные технологии» С.-Петербургского государственного института точной механики и оптики (технического университета) — СПбГИТМО (ТУ), е-mail: levnaumov@mail.ru.

Шалыто Анатолий Абрамович — профессор кафедры «Компьютерные технологии» СПбГИТМО (ТУ), е-mail: mail@avrorasystems.com (для Шалыто); : http://is.ifmo.ru.

Источник: https://www.osp.ru/pcworld/2003/08/166226

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