Изменения

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

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

6005 байт добавлено, 19:13, 4 сентября 2022
м
rollbackEdits.php mass rollback
{{В разработке}}
 
= Базовые определения =
{{Определение
Движение "электрона" в "цепи" происходит со следующими закономерностями:
* При прохождении электроном разветвления "цепи", в каждое из новых направлений уходит по "электрону";
* При одновременном столкновении двух трёх и более "электронов", они исчезают.
* При толщине "провода" больше $2$, "электроны" начинают двигаться хаотично.
|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{—$S\;$ осуществляется путем возбужденияспециальное;}\\ \end{cases}\end{equation*}</tex><br>::: <tex> \alpha = 0, \dots, 3 </tex> {{---}} выходное направление (вправо, после которого автомат проходит ряд сенситивных состоянийвверх, в конечном счетевлево, переходя в состояние вниз);::: <tex>\varepsilon = \begin{equation*} \begin{cases} 0 &\text{—$C\;$ или покой,}\\ 1 &\text{—$T\;$возбуждение;}\\ \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. Чувствительные состояния $US, \; 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>Более подробно Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и правила перехода данного автомата описаны два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в §5состоянии $T_1$, выходные направления которых ориентированы на "нейрон".3 книги Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "Физика процессов эволюциивыходом"нейрона.<ref name=br><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 PICTURES'''<br>
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.
Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"<ref name="neuman_automata"/>.
== Автомат Лэнгтона ==
'''Тьюрмит'''<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>
1632
правки

Навигация