Модели клеточных автоматов — различия между версиями
Cuciev (обсуждение | вклад) м (Turmits: name fixed) |
Cuciev (обсуждение | вклад) м (Release... I believe?) |
||
(не показано 29 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
− | |||
− | |||
= Базовые определения = | = Базовые определения = | ||
{{Определение | {{Определение | ||
Строка 53: | Строка 51: | ||
}} | }} | ||
В соответствии с определением, код может быть вычислен следующим образом: | В соответствии с определением, код может быть вычислен следующим образом: | ||
− | + | # Определить все возможные конфигурации окрестности данной ячейки; | |
− | + | # Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию; | |
− | + | # Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации; | |
− | + | # Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама. | |
− | + | <br> | |
Далее в статье будут приведены наиболее известные правила.<br> | Далее в статье будут приведены наиболее известные правила.<br> | ||
Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге. | Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге. | ||
− | |||
− | |||
=== Правило 30 === | === Правило 30 === | ||
Строка 68: | Строка 64: | ||
'''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1). | '''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1). | ||
}} | }} | ||
+ | [[Файл:Rule30.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 30]] | ||
+ | <br> | ||
Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:<br> | Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:<br> | ||
{| class="wikitable" align="center" style="text-align:center" | {| class="wikitable" align="center" style="text-align:center" | ||
Строка 84: | Строка 82: | ||
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. | Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. | ||
}} | }} | ||
+ | [[Файл:Rule90.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 90]] | ||
+ | <br> | ||
Правила перехода для Правила 90: | Правила перехода для Правила 90: | ||
{| class="wikitable" style="text-align: center" | {| class="wikitable" style="text-align: center" | ||
Строка 101: | Строка 101: | ||
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. | Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. | ||
}} | }} | ||
+ | [[Файл:Rule110.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 110]] | ||
+ | <br> | ||
Правила перехода для Правила 110: | Правила перехода для Правила 110: | ||
{| class="wikitable" style="text-align: center" | {| class="wikitable" style="text-align: center" | ||
Строка 111: | Строка 113: | ||
|} | |} | ||
Так как <tex>1101110_2 = {110}_{10}</tex>, данное правило называется Правилом 110. | Так как <tex>1101110_2 = {110}_{10}</tex>, данное правило называется Правилом 110. | ||
+ | <br> | ||
+ | <br> | ||
+ | <br> | ||
+ | <br> | ||
+ | <br> | ||
+ | <br> | ||
+ | <br> | ||
+ | <br> | ||
+ | |||
=== Правило 184 === | === Правило 184 === | ||
Строка 117: | Строка 128: | ||
'''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br> | '''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br> | ||
}} | }} | ||
+ | [[Файл:Rule184.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 184]] | ||
+ | <br> | ||
Правила перехода для Правила 184: | Правила перехода для Правила 184: | ||
{| class="wikitable" style="text-align:center;" | {| class="wikitable" style="text-align:center;" | ||
Строка 156: | Строка 169: | ||
В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm</ref>. | В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm</ref>. | ||
− | ''' TODO: ADD | + | ''' TODO: ADD PICTURES''' |
==== Устойчивые фигуры ==== | ==== Устойчивые фигуры ==== | ||
Строка 330: | Строка 343: | ||
|id=neiman_auto | |id=neiman_auto | ||
|definition= | |definition= | ||
− | '''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref>Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями. | + | '''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref name="neuman_automata">Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями. |
}} | }} | ||
− | === Состояния | + | === Состояния === |
− | + | Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку: | |
− | + | * [[#neiman_neighborhood | Окрестность фон Неймана]]: <tex>v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1)</tex>; | |
− | + | * Клетки, дополняющие окрестность фон Неймана до [[#moore_neighborhood | окрестности Мура]]: <tex>v^4 = (1, 1) \;\;\; v^5 = (-1, 1) \;\;\; v^6 = (-1, -1) \;\;\; v^7 = (1, -1)</tex><br><br> | |
− | + | Состояние клетки $\vartheta$ на $t$-ом шаге: <tex>n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; \alpha = 0, \dots , 3), F</tex> {{---}} функция переходов.<br> | |
− | |||
− | |||
− | |||
− | |||
− | |||
<br> | <br> | ||
− | ' | + | Состояния клеток рассматриваемого автомата делятся на $4$ различных класса:<br> |
− | <br> | + | 1. Основное состояние <tex>U</tex> (невозбужденное).<br> |
− | + | 2. Транзитивные состояния <tex>T_{u\alpha\varepsilon}</tex>, где: | |
− | <br> | + | ::: <tex> |
− | + | u = | |
+ | \begin{equation*} | ||
+ | \begin{cases} | ||
+ | 0 &\text{—$\;$ обычное,}\\ | ||
+ | 1 &\text{—$\;$ специальное;}\\ | ||
+ | \end{cases} | ||
+ | \end{equation*} | ||
+ | </tex><br> | ||
+ | ::: <tex> \alpha = 0, \dots, 3 </tex> {{---}} выходное направление (вправо, вверх, влево, вниз); | ||
+ | ::: <tex> | ||
+ | \varepsilon = | ||
+ | \begin{equation*} | ||
+ | \begin{cases} | ||
+ | 0 &\text{—$\;$ покой,}\\ | ||
+ | 1 &\text{—$\;$ возбуждение;}\\ | ||
+ | \end{cases} | ||
+ | \end{equation*} | ||
+ | </tex><br> | ||
+ | 3. Конфлюэнтные состояния <tex>C_{\varepsilon{\varepsilon}'}</tex>, где: | ||
+ | ::: <tex> | ||
+ | \varepsilon = | ||
+ | \begin{equation*} | ||
+ | \begin{cases} | ||
+ | 0 &\text{—$\;$ покой,}\\ | ||
+ | 1 &\text{—$\;$ возбуждение;}\\ | ||
+ | \end{cases} | ||
+ | \end{equation*} | ||
+ | </tex><br> | ||
+ | ::: <tex> | ||
+ | {\varepsilon}' = | ||
+ | \begin{equation*} | ||
+ | \begin{cases} | ||
+ | 0 &\text{—$\;$ покой на следующем такте,}\\ | ||
+ | 1 &\text{—$\;$ возбуждение на следующем такте;}\\ | ||
+ | \end{cases} | ||
+ | \end{equation*} | ||
+ | </tex><br> | ||
+ | 4. Чувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, S_{10} \;, S_{11}$. | ||
+ | <br><br> | ||
+ | Далее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит<ref name="neuman_automata"/> аналогию с системой нейронных связей, аналогичным образом строя автомат.<br><br> | ||
+ | Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс.<br><br> | ||
+ | Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в состоянии $T_1$, выходные направления которых ориентированы на "нейрон". Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.<br><br> | ||
+ | По аналогии с нейронными сетями, автомат должен иметь возможность "расщеплять" передаваемый сигнал, т.е. обеспечить возможность передачи его нескольким клеткам сразу. Данную функцию выполняют конфлюэнтные состояния, по определению имея несколько "выходов" и один "вход".<br><br> | ||
+ | Состояния $S_{\Sigma0}$ и $S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов. | ||
+ | |||
+ | === Правила переходов === | ||
+ | Функция переходов $F$ определяется следующими соотношениями: | ||
+ | |||
+ | # Клетка в состоянии $T_{u\alpha\varepsilon}$ перейдет в состояние: | ||
+ | ## $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u'{\alpha}'{\vartheta}'}$; | ||
+ | ## $T_{u{\alpha}1}$, если пункт $1.1$ не выполнен, и среди ее соседей найдется клетка, удовлетворяющая одному из условий: | ||
+ | ### ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'} \neq -v^\alpha$ в состоянии $T_{u{\alpha}'1}$; | ||
+ | ### ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{\beta} \neq -v^\alpha, \; \beta = 0,\dots, 3$ в состоянии $C_1$; | ||
+ | ## $T_{u{\alpha}0}$ во всех остальных случаях. | ||
+ | # Клетка в состоянии $C_{\varepsilon\varepsilon'}$ перейдет в состояние: | ||
+ | ## $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{1{\alpha}'1}$; | ||
+ | ## $C_{\varepsilon'1}$, если пункт $2.1$ не выполнен, и среди ее соседей найдется клетка ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{0{\alpha}'1}$, а все остальные такие клетки не будут находиться в состоянии $T_{0{\alpha}'0}$; | ||
+ | ## $n_{\vartheta}^{t} = C_{\varepsilon'0}$, иначе. | ||
+ | # Клетка в состоянии $U$ перейдет в состояние: | ||
+ | ## $S_0$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$; | ||
+ | ## $U$ во всех остальных случаях. | ||
+ | # Клетка в состоянии $S_\Sigma, \; \Sigma=0,\dots,000$ перейдет в состояние: | ||
+ | ## $S_{\Sigma1}$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$; | ||
+ | ## $S_{\Sigma0}$, во всех остальных случаях. | ||
=== Принцип работы === | === Принцип работы === | ||
− | |||
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана. | Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана. | ||
+ | Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"<ref name="neuman_automata"/>. | ||
== Автомат Лэнгтона == | == Автомат Лэнгтона == | ||
Строка 379: | Строка 450: | ||
=== Принцип работы === | === Принцип работы === | ||
− | ''' | + | <gallery mode="packed" widths=75px heights=200px> |
+ | Image:langton_start.jpg|''Начальная конфигурация'' | ||
+ | Image:langton_copy.jpg|''Порожденная копия после 151 такта'' | ||
+ | </gallery> | ||
+ | |||
* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$; | * Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$; | ||
* Поворот ленты влево достигается путем передачи на ее конец сигнала $40$; | * Поворот ленты влево достигается путем передачи на ее конец сигнала $40$; | ||
Строка 389: | Строка 464: | ||
'''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо. | '''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо. | ||
}} | }} | ||
− | + | [[Файл:Turmite_Langton_ant.png|thumb|300px|right|Результат работы [https://ru.wikipedia.org/wiki/Муравей_Лэнгтона муравья Лэнгтона] после 27731 итераций]] | |
Каждая строка программы записывается в следующем виде: | Каждая строка программы записывается в следующем виде: | ||
<pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre> | <pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre> | ||
− | |||
− | |||
<br> | <br> | ||
[[Игра «Жизнь»]] эмулируется<ref name="mitin" /> с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.<br> | [[Игра «Жизнь»]] эмулируется<ref name="mitin" /> с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.<br> |
Текущая версия на 19:33, 19 января 2021
Содержание
Базовые определения[править]
Определение: |
Клеточный автомат[1] представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии. Множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$. |
Определение и основные свойства линейного клеточного автомата содержатся в статье "линейный клеточный автомат, эквивалентность МТ".
Определение: |
Окрестность Мура[2] ячейки — совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой. Окрестность Мура порядка в двумерном случае представляет собой квадрат со стороной [3]. |
Определение: |
Окрестность фон Неймана[4] ячейки — совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой. |
Классификация клеточных автоматов[править]
Классификация Вольфрама[править]
Определение: |
Классы Вольфрама[5] — классификация клеточных автоматов, основанная на их поведении. |
Классы, предложенные С. Вольфрамом[6]
Классификация Эпштейна[править]
На ряд серьезных недостатков классификации С. Вольфрама указывал[7] Д. Эпштейн.
Один из них состоял в невозможности за разумное время проверить принадлежность клеточного автомата к какому-либо классу для большого числа клеточных автоматов.
В свою очередь он предложил систему классификации двухмерных двоичных клеточных автоматов, призванную выделять кандидатов в универсальные клеточные автоматы.
Классы, предложенные Д. Эпштейном[6]
Однако, данная классификация так же имела серьезные проблемы, и, в конечном счете, не удовлетворяла своему назначению. Более подробные описания данных классификаций, а также других наиболее распространенных, можно найти в работе П.С. Скакова[6]. В ней, в том числе, были выделены основные достоинства и недостатки различных классификаций, и предложена новая, являющаяся уточнением и модификацией существующих и решающая многие их проблемы.
Одномерные клеточные автоматы[править]
Коды Вольфрама[править]
Определение: |
Код Вольфрама — система именования клеточных автоматов (как правило, ЛКА), предложенная С. Вольфрамом в 1983 году[8]. Данная система основана на наблюдении, что таблица, определяющая новое состояние каждой ячейки в автомате, как функция состояний в его окрестности, может интерпретироваться как число из -цифр в -арной позиционной системе счисления, где — число состояний, которое может иметь каждая ячейка в автомате, — число конфигураций окрестности, а — радиус окрестности. |
В соответствии с определением, код может быть вычислен следующим образом:
- Определить все возможные конфигурации окрестности данной ячейки;
- Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;
- Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации;
- Интерпретируя полученный список состояний как -арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.
Далее в статье будут приведены наиболее известные правила.
Во всех случаях рассматриваются ЛКА с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге.
Правило 30[править]
Определение: |
Правило 30 — ЛКА с двумя состояниями (0 и 1). |
Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:
Текущее состояние трёх соседних клеток | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
Новое состояние центральной клетки | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Так как
, данное правило называется Правилом 30.Правило 90[править]
Определение: |
Правило 90 — ЛКА с двумя состояниями (0 и 1). Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. |
Правила перехода для Правила 90:
Текущее состояние трёх соседних клеток | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
Новое состояние центральной клетки | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Так как
, данное правило называется Правилом 90.Правило 110[править]
Определение: |
Правило 110 — ЛКА с двумя состояниями (0 и 1). Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей. |
Правила перехода для Правила 110:
Текущее состояние трёх соседних клеток | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
Новое состояние центральной клетки | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Так как
Правило 184[править]
Определение: |
Правило 184 — ЛКА с двумя состояниями (0 и 1). |
Правила перехода для Правила 184:
Текущее состояние трёх соседних клеток | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
Новое состояние центральной клетки | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
Так как
, данное правило называется Правилом 184.Клеточные автоматы на двумерной решетке[править]
Игра «Жизнь»[править]
Некоторые из приведенных далее определений были взяты с этого[9] сайта, а также со смежных с нем страниц.
Определение: |
«Жизнь» — клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. Состояние, в которое перейдет клетка на следующем шаге, зависит от состояний ее соседей в окрестности Мура. |
Основную информацию по игре вы можете найти в статье "игра «Жизнь»". В данном разделе будут рассмотрены лишь основные типы и примеры конфигураций данной игры.
Состояния и правила переходов[править]
Название состояния | Цвет | Переходит в cостояние |
---|---|---|
«Живая клетка» | Белый | «мертвая клетка», если имеет ровно меньше двух или больше трех соседей в состоянии «живая клетка». |
«Мертвая клетка» | Черный | «живая клетка», если имеет ровно трех соседей в состоянии «живая клетка». |
Основные элементы[править]
В данном разделе используются термины из «Словаря Жизни»[10].
TODO: ADD PICTURES
Устойчивые фигуры[править]
Определение: |
Устойчивый образец — объект, который является собственным родителем. |
Определение: |
Натюрморт[11] — устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть. |
Определение: |
Псевдонатюрморт — устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов. |
Долгожители[править]
Определение: |
Долгожитель — конфигурация из 10 или меньшего числа клеток, которым необходимо не менее 50 поколений для стабилизации[12]. |
Осцилляторы[править]
Определение: |
Осциллятор — конфигурация клеточного автомата, которая после конечного числа поколений повторяется в изначальном виде и положении. |
Определение: |
Период осциллятора — минимальное число поколений, через которое осциллятор возвращается в исходное состояние. |
Двигающиеся фигуры[править]
Определение: |
Космический корабль — конфигурация, которая через определённое количество поколений вновь появляется без дополнений или потерь, но со смещением относительно исходного положения. |
Определение: |
Период космического корабля — минимальное число поколений, за которое космический корабль смещается. |
Ружья[править]
Определение: |
Ружье — класс конфигураций, у которых основная часть циклически повторяется, как у осцилляторов, а также периодически создаёт космические корабли, которые удаляются от ружья. Данная конфигурация имеет два периода: период создания космических кораблей и период повторения состояний ружья. |
Паровозы[править]
Определение: |
Паровоз — объект, который движется по полю подобно космическому кораблю, но при этом ещё и оставляет за собой след из других объектов. |
Определение: |
Грабли — паровозы, оставляющие за собой след исключительно из космических кораблей. |
Пожиратели[править]
Определение: |
Пожиратель — конфигурация, способная уничтожить космический корабль и восстановиться после контакта. |
Отражатели[править]
Определение: |
Отражатель — натюрморт или периодическая конфигурация, способная изменить направление движения другой фигуры определенного типа на 90° или 180°, восстанавливая свою структуру после отражения. |
Определение: |
Время восстановления отражателя — минимальное число поколений, которое должно проходить между столкновением с другими фигурами, чтобы отражатель успевал восстановиться. |
Размножители[править]
Определение: |
Размножитель — конфигурация, растущая квадратично, производя множество копий вторичной конфигурации, каждая из которых производит множество копий третичной конфигурации. |
Существует несколько видов[13] размножителей, отличающихся между собой относительной подвижностью полученных конфигураций. Виды кодируются при сочетаниями трех букв, описывающие, соответственно, первичную, вторичную и третичную конфигурации: Д — движущаяся, Н — неподвижная:
- НДД — ружьё, вырабатывающее грабли;
- ДНД — паровоз, вырабатывающий ружья;
- ДДН — грабли, вырабатывающий паровозы;
- ДДД — грабли, вырабатывающий грабли.
Wireworld[править]
Определение: |
Клеточный автомат Wireworld[14] представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний. |
Состояния и правила переходов[править]
Название состояния | Цвет | Переходит в состояние |
---|---|---|
Пустая клетка | Черный | |
Проводник | Желтый | «голова электрона», если имеет ровно одного или двух соседей в состоянии «голова электрона» |
Голова электрона | Красный | «хвост электрона» |
Хвост электрона | Синий | «проводник» |
Общие закономерности[править]
Движение "электрона" в "цепи" происходит со следующими закономерностями:
- При прохождении электроном разветвления "цепи", в каждое из новых направлений уходит по "электрону";
- При одновременном столкновении двух и более "электронов", они исчезают.
- При толщине "провода" больше $2$, "электроны" начинают двигаться хаотично.
Основные элементы[править]
В данной статье приведены лишь основные простейшие элементы, которые можно составить в Wireworld.
Большое количество примеров приведено в Mirek's Cellebration[15] и Zillions of Games[16], WireWorld[17]; с помощью элементов Wireworld также был построен[18] компьютер.
Тактовый генератор[править]
Данный элемент используется для получения электронов, так как при каждом прохождении разветвления электроном, движущимся по петле генератора, образуется новый электрон. Частота появления электронов регулируется длиной петли.
Диод[править]
Данный элемент действует точно так же, как одноименный элемент[19] электрической цепи.
Логические элементы OR, XOR и NAND[править]
Данный элемент действует точно так же, как и одноименные логические элементы[20][21][22].
Самовоспроизводящиеся клеточные автоматы[править]
В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"[23]:
«
- Логическая универсальность.
- При каких условиях определенный класс автоматов логически универсален?
- Существует ли логически универсальный автомат?
- Конструируемость.
- Может ли один автомат быть построен другим автоматом?
- Какой класс автоматов может быть построен каким-то автоматом?
- Конструктивная универсальность.
- Существует ли конструктивно универсальный автомат? (т. е. автомат, способный построить любой автомат)
- Самовоспроизведение.
- Существует ли самовоспроизводящийся автомат?
- Существует ли автомат, который, помимо самовоспроизведения, может решать и другие задачи?
- Эволюция.
- Может ли при конструировании автомата автоматом происходить усложнение типа автомата?
- Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату? (при надлежащем определении понятия эффективности)
- ».
В то время, как Тьюринг доказал, что машина Тьюринга является логически универсальной, Дж. фон Нейман построил автомат[24], удовлетворяющий всем пяти свойствам. Одна из таких моделей будет описана далее.
Автомат фон Неймана[править]
Определение: |
Автомат фон Неймана (клеточная модель самовоспроизведения[25]) — объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями. |
Состояния[править]
Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:
- Окрестность фон Неймана: ;
- Клетки, дополняющие окрестность фон Неймана до окрестности Мура:
Состояние клетки $\vartheta$ на $t$-ом шаге:
Состояния клеток рассматриваемого автомата делятся на $4$ различных класса:
1. Основное состояние (невозбужденное).
2. Транзитивные состояния , где:
-
- — выходное направление (вправо, вверх, влево, вниз);
-
-
3. Конфлюэнтные состояния
, где:4. Чувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, S_{10} \;, S_{11}$.
Далее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит[25] аналогию с системой нейронных связей, аналогичным образом строя автомат.
Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс.
Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в состоянии $T_1$, выходные направления которых ориентированы на "нейрон". Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.
По аналогии с нейронными сетями, автомат должен иметь возможность "расщеплять" передаваемый сигнал, т.е. обеспечить возможность передачи его нескольким клеткам сразу. Данную функцию выполняют конфлюэнтные состояния, по определению имея несколько "выходов" и один "вход".
Состояния $S_{\Sigma0}$ и $S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов.
Правила переходов[править]
Функция переходов $F$ определяется следующими соотношениями:
- Клетка в состоянии $T_{u\alpha\varepsilon}$ перейдет в состояние:
- $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u'{\alpha}'{\vartheta}'}$;
- $T_{u{\alpha}1}$, если пункт $1.1$ не выполнен, и среди ее соседей найдется клетка, удовлетворяющая одному из условий:
- ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'} \neq -v^\alpha$ в состоянии $T_{u{\alpha}'1}$;
- ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{\beta} \neq -v^\alpha, \; \beta = 0,\dots, 3$ в состоянии $C_1$;
- $T_{u{\alpha}0}$ во всех остальных случаях.
- Клетка в состоянии $C_{\varepsilon\varepsilon'}$ перейдет в состояние:
- $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{1{\alpha}'1}$;
- $C_{\varepsilon'1}$, если пункт $2.1$ не выполнен, и среди ее соседей найдется клетка ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{0{\alpha}'1}$, а все остальные такие клетки не будут находиться в состоянии $T_{0{\alpha}'0}$;
- $n_{\vartheta}^{t} = C_{\varepsilon'0}$, иначе.
- Клетка в состоянии $U$ перейдет в состояние:
- $S_0$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$;
- $U$ во всех остальных случаях.
- Клетка в состоянии $S_\Sigma, \; \Sigma=0,\dots,000$ перейдет в состояние:
- $S_{\Sigma1}$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$;
- $S_{\Sigma0}$, во всех остальных случаях.
Принцип работы[править]
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана. Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"[25].
Автомат Лэнгтона[править]
Примером более простого самовоспроизводящегося клеточного автомата является автомат Лэнгтона[24].
Также интерес представляет Муравей Лэнгтона[26], разработанный в 1986 году Крисом Лэнгтоном и являющимся, по сути, двумерной машиной Тьюринга с 2 символами и 4 состояниями[27].
Определение: |
Автомат Лэнгтона — двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками. В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей. |
Состояния[править]
Сигнальные состояния[править]
Состояния $3-7$ относят к классу сигнальных:
- $3$ используется при повороте;
- $5$ и $6$ используются для самовоспроизведения.
Служебные состояния[править]
Состояния $0-2$ относят к классу служебных:
- $0$, идущее вслед за сигнальным задает направление распространения сигнала;
- $1$ является «несущей лентой» сигнала;
- Из клеток в состоянии $2$ строятся «стенки» автомата.
Принцип работы[править]
- Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;
- Поворот ленты влево достигается путем передачи на ее конец сигнала $40$;
- Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.
Тьюрмиты[править]
Определение: |
Тьюрмит[24] — это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо. |

Каждая строка программы записывается в следующем виде:
<текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние>
Игра «Жизнь» эмулируется[24] с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.
В области исследований модели ДНК при моделировании активно используются взаимодействующие и плиточные тьюрмиты[24] .
См.также[править]
- Линейный клеточный автомат, эквивалентность МТ
- Машина Тьюринга
- Линейный ограниченный автомат
- Автомат фон Неймана
- Муравей Лэнгтона
- Лобанов А.И. Модели клеточных автоматов[28]
Литература[править]
- ↑ Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=Список_заданий_по_ДМ_2к_2020_весна
- ↑ Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура
- ↑ Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html
- ↑ Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/Окрестность_фон_Неймана
- ↑ Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8
- ↑ 6,0 6,1 6,2 Скаков П.С. Классификация поведения одномерных клеточных автоматов. СПб., 2007 — URL: http://is.ifmo.ru/diploma-theses/_skakov_master.pdf
- ↑ Eppstein D. Classification of Cellular Automata. http://www.ics.uci.edu/~eppstein/ca/wolfram.html
- ↑ Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55: 601–644
- ↑ Игра "Жизнь". URL: https://ru.wikipedia.org/wiki/Игра_«Жизнь»
- ↑ «Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm
- ↑ Eric Weisstein. Still Life
- ↑ Gardner, M. (1983). "The Game of Life, Part III". Wheels, Life and Other Mathematical Amusements: 246
- ↑ Breeder – from Eric Weisstein's Treasure Trove of Life
- ↑ Трофимов Д., Наумов Л. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007. URL: http://is.ifmo.ru/works/wireworld/
- ↑ "Mirek's Cellebration". URL:http://mirekw.com/ca/index.html
- ↑ "Zillions of Games". URL:http://zillionsofgames.com
- ↑ "WireWorld". URL:http://karl.kiwi.gen.nz/CA-Wireworld.html.
- ↑ "The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html
- ↑ Диод. URL: https://ru.wikipedia.org/wiki/Диод
- ↑ Дизъюнкция. URL: https://ru.wikipedia.org/wiki/Дизъюнкция
- ↑ Исключающее «или». URL: https://ru.wikipedia.org/wiki/Исключающее_«или»
- ↑ NAND (логический элемент). URL: https://ru.wikipedia.org/wiki/Штрих_Шеффера
- ↑ Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, 2001. - 328 с.
- ↑ 24,0 24,1 24,2 24,3 24,4 Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf
- ↑ 25,0 25,1 25,2 Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971
- ↑ Langton, Chris G. (1986). "Studying artificial life with cellular automata", 120–149
- ↑ Mária Bieliková, Gerhard Friedrich, Georg Gottlob. SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012, Proceedings. — Springer, 2012. — P. 394. — ISBN 978-3-642-27660-6.
- ↑ Лобанов А.И. Модели клеточных автоматов // Компьютерные исследования и моделирование, 2010, т. 2, № 3, с. 273-293. URL: http://vst.ics.org.ru/uploads/crmissues/kim_2010_2_3/crm10304.pdf