Изменения

Перейти к: навигация, поиск

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

4777 байт добавлено, 01:38, 27 июня 2020
м
Fon Neuman Automat: decription
{{Определение
|definition=
'''Клеточный автомат'''<ref>Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B9_%D0%BF%D0%BE_%D0%94%D0%9C_2%D0%BA_2020_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0Список_заданий_по_ДМ_2к_2020_весна</ref> представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии.<br><br>
Множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$.<br>
Изначально все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от $1$ до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$). <br><br>
|id=moore_neighborhood
|definition=
'''Окрестность Мура'''<ref>Окрестность Мура. URL: https://ru.wikipedia.org/wiki/%D0%9E%D0%BA%D1%80%D0%B5%D1%81%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%9C%D1%83%D1%80%D0%B0Окрестность_Мура</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.<br>
Окрестность Мура порядка <tex>r</tex> в двумерном случае представляет собой квадрат со стороной <tex>2r + 1</tex><ref>Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html</ref>.
}}
|id=neiman_neighborhood
|definition=
'''Окрестность фон Неймана'''<ref>Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/%D0%9E%D0%BA%D1%80%D0%B5%D1%81%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D1%84%D0%BE%D0%BD_%D0%9D%D0%B5%D0%B9%D0%BC%D0%B0%D0%BD%D0%B0Окрестность_фон_Неймана</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.}} {{Определение|id=edem_def|definition='''Райский сад'''<ref name="edem">Сад Эдема (конфигурация клеточного автомата). URL: https://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%B4_%D0%AD%D0%B4%D0%B5%D0%BC%D0%B0_(%D0%BA%D0%BE%D0%BD%D1%84%D0%B8%D0%B3%D1%83%D1%80%D0%B0%D1%86%D0%B8%D1%8F_%D0%BA%D0%BB%D0%B5%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0)</ref> {{---}} конфигурация КА, которая не может появиться в результате «эволюции», потому что не имеет предшественников.}}{{Теорема|id=edem_theorem|about=сада Эдема|statement=Клеточный автомат в евклидовой вселенной является локально инъективным тогда и только тогда, когда он сюръективен.Другими словами, теорема утверждает, что сады Эдема существуют только в тех автоматах, в которых существуют близнецы.Данная теорема была выдвинута и доказана Эдвардом Муром<ref>Moore, E. F. (1962), Machine models of self-reproduction, Proc. Symp. Applied Mathematics Т. 14: 17–33</ref>.
}}
{{Определение
|definition=
'''Классы Вольфрама'''<ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} система классификации классификация клеточных автоматов, основанная на их поведении.
}}
}}
В соответствии с определением, код может быть вычислен следующим образом:
'''Алгоритм вычисления кода Вольфрама:''' 1. # Определить все возможные конфигурации окрестности данной ячейки; 2. # Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию; 3. # Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации; 4. # Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.<br>
Далее в статье будут приведены наиболее известные правила.<br>
Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге.
 
'''TODO: ADD PICTIRES'''
=== Правило 30 ===
'''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).
}}
[[Файл:Rule30.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 30]]
<br>
Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:<br>
{| class="wikitable" align="center" style="text-align:center"
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
}}
[[Файл:Rule90.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 90]]
<br>
Правила перехода для Правила 90:
{| class="wikitable" style="text-align: center"
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
}}
[[Файл:Rule110.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 110]]
<br>
Правила перехода для Правила 110:
{| class="wikitable" style="text-align: center"
|}
Так как <tex>1101110_2 = {110}_{10}</tex>, данное правило называется Правилом 110.
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
 
=== Правило 184 ===
'''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>
}}
[[Файл:Rule184.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 184]]
<br>
Правила перехода для Правила 184:
{| class="wikitable" style="text-align:center;"
= Клеточные автоматы на двумерной решетке =
== Игра «Жизнь» ==
Некоторые из приведенных далее определений были взяты с этого<ref>Игра "Жизнь". URL: https://ru.wikipedia.org/wiki/%D0%98%D0%B3%D1%80%D0%B0_%C2%AB%D0%96%D0%B8%D0%B7%D0%BD%D1%8C%C2%BBИгра_«Жизнь»</ref> сайта, а также со смежных с нем страниц.
{{Определение
|definition=
В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm</ref>.
''' TODO: ADD PICTIRESPICTURES'''
==== Устойчивые фигуры ====
* ДДН {{---}} грабли, вырабатывающий паровозы;
* ДДД {{---}} грабли, вырабатывающий грабли.
 
==== Райский сад ====
[[#edem_theorem | Теорема сада Эдема]] применима к «Жизни»: конфигурация, состоящая из одной «живой клетки» переходит в ту же конфигурацию, что и конфигурация, состоящая только из «мертвых» клеток.
Следовательно, в «Жизни» существуют сады Эдема.
== Wireworld ==
|id=neiman_auto
|definition=
'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<refname="neuman_automata">Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями.
}}
=== Состояния и правила переходов ===Автомат Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:* [[#neiman_neighborhood | Окрестность фон Неймана имеет ]]: <tex>N v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = 29(-1, 0) \;\;\; v^3 = (0, -1)</tex> различных состояний;* Клетки, дополняющие окрестность фон Неймана до [[#moore_neighborhood | окрестности Мура]]:<brtex># Транзитивные состояния v^4 = (импульсы1, 1) $T_{u\alpha;\;\varepsilon}$. Определяются:## Направлением движения.## Статусом ; v^5 = (покой/возбуждение-1, обычное/специальное1)\;# Конфлюэнтные состояния <tex>C_{\varepsilon{;\varepsilon}'}</tex>. Определяются:## Статусом ; v^6 = (покой/возбуждение-1, -1)\;\;\;## Статусом на следующем такте v^7 = (покой/возбуждение1, -1);# Основное состояние </tex>U</texbr><br> (невозбужденное);# Чувствительные (сенситивные) состояния Состояние клетки $\vartheta$ на $t$-ом шаге: <tex>S_n_{t}^{\Sigmavartheta}= F(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; \alpha = 0, \dots , 3), F</tex>{{---}} функция переходов.<br>
<br>
Состояния клеток рассматриваемого автомата делятся на $4$ различных класса:<br>1. Основное состояние <tex>U</tex> (невозбужденное).<br>2. Транзитивные состояния <tex>T_{u\alpha\varepsilon}</tex>, где:::: <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}''' TODO}</tex>, где:::: ADD SCHEME'''<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{—$U\;$ в возбуждение на следующем такте;}\\ \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>Для передачи информации между клетками по цепочке из клеток же вводятся состояния $CT$ или , причем наличие нейронного импульса регулируется параметром $T\varepsilon$. Оба конечных состояния могут попеременно находиться в возбужденной и невозбужденной формеТак как передача должна быть направленным процессом, оставаться неизменными или переходить снова в вводится параметр $U\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс.<br><br>Более подробно Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и правила перехода данного автомата описаны два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в §5состоянии $T_1$, выходные направления которых ориентированы на "нейрон".3 книги Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "Физика процессов эволюциивыходом"нейрона.<br><ref name=br>По аналогии с нейронными сетями, автомат должен иметь возможность "расщеплять" передаваемый сигнал, т.е. обеспечить возможность передачи его нескольким клеткам сразу. Данную функцию выполняют конфлюэнтные состояния, по определению имея несколько "выходов" и один "physicsвход" /.<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}$, во всех остальных случаях.
=== Принцип работы ===
''' TODO: ADD PICS'''<br>
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.
Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"<ref name="neuman_automata"/>.
== Автомат Лэнгтона ==
|definition=
'''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками.<br>
 В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.<br>Сигнальная лента несет информацию, необходимую для создания копии автомата.
}}
Сигнальная лента несет информацию, необходимую для создания копии автомата.<br>
=== Состояния ===
=== Принцип работы ===
<gallery mode="packed" widths=75px heights=200px>Image:langton_start.jpg|''Начальная конфигурация' TODO'Image: ADD PICTURESlangton_copy.jpg|''Порожденная копия после 151 такта''<br/gallery
* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;
* Поворот ленты влево достигается путем передачи на ее конец сигнала $40$;
* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.
= Тюрьмиты Тьюрмиты =
{{Определение
|definition=
'''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.
}}
[[Файл:Turmite_Langton_ant.png|thumb|300px|right|Результат работы [https://ru.wikipedia.org/wiki/Муравей_Лэнгтона муравья Лэнгтона] после 27731 итераций]]
Каждая строка программы записывается в следующем виде:
<pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre>
<br>
'''TODO: ADD PICTURES'''
<br>
[[Игра «Жизнь»]] эмулируется<ref name="mitin" /> с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.<br>
* [[Линейный ограниченный автомат]]
* [https://ru.wikipedia.org/wiki/Автомат_фон_Неймана Автомат фон Неймана]
* [https://ru.wikipedia.org/wiki/%D0%9C%D1%83%D1%80%D0%B0%D0%B2%D0%B5%D0%B9_%D0%9B%D1%8D%D0%BD%D0%B3%D1%82%D0%BE%D0%BD%D0%B0 Муравей_Лэнгтона Муравей Лэнгтона]* Лобанов А.И. Модели клеточных автоматов<ref>Лобанов А.И. Модели клеточных автоматов // Компьютерные исследования и моделирование, 2010, т. 2, № 3, с. 273-293. URL: http://vst.ics.org.ru/uploads/crmissues/kim_2010_2_3/crm10304.pdf</ref>
= Литература =
386
правок

Навигация