436
правок
Изменения
Fon Neuman Automat: pre-refactoring
Более подробно состояния и правила перехода данного автомата описаны в §5.3 книги "Физика процессов эволюции"<ref name="physics" />.
=== Формальное описание ===
''' TODO: WRITE OWN FORMAL DECRIPTION'''
Данное описание взято из §5.3 книги "Физика процессов эволюции"<ref name="physics" />:<br>
"
Как было сказано выше, [[#neiman_auto | автомат фон Неймана]] представляет клеточный автомат, у которого каждая клетка может находиться в 29 состояниях. Клеточный автомат состоит из многих однотипных автоматов, расположенных в узлах решетки; выход каждого автомата служит входом для [[#neiman_neighborhood | соседних клеток]].<br>
Нумерует клетки радиус-вектор <tex>\vartheta = (i, j), \; i,j = 0, \pm 1, \pm 2, \dots</tex>.
<br>
<br>
{{Определение
|definition=
Назовем '''ближайшими соседями''' клетки те клетки, что лежат в ее [[#neiman_neighborhood | окрестности фон Неймана]]; клетки, дополняющие [[#neiman_neighborhood | окрестность фон Неймана]] до [[#moore_neighborhood | окрестность Мура]], назовем '''ближними соседями'''.
}}
<br>
Определим восемь векторов расстояния:<br>
<tex>v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1) \;\;\; v^4 = (1, 1) \;\;\; v^5 = (-1, 1) \;\;\; v^6 = (-1, -1) \;\;\; v^7 = (1, -1)</tex><br>
Тогда <tex>\vartheta + v^\alpha,\; \alpha = 0, \dots , 3</tex> {{---}} ближайшие соседи, а <tex>\vartheta + v^\alpha,\; \alpha = 7, \dots , 7</tex> {{---}} ближние.
<br><br>
Время дискретно, т.е. изменяется по тактам: <tex>t = 0, \pm 1, \pm 2, \dots</tex>, на каждом такте каждая клетка <tex>\vartheta</tex> находится в одном из <tex>n</tex> состояний <tex>n = 0, \dots , N - 1</tex>, т.е. состояние на такте <tex>t</tex> есть <tex>n_{t}^{\vartheta}</tex>.
<br><br>
Состояния изменяются по правилу перехода <tex>F</tex>, одинаковому для всех клеток (внутренняя однородность):<br>
: <tex>n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; \alpha = 0, \dots , 3)</tex><br>
В соотношении выше <tex>F</tex> зависит от <tex>5</tex> переменных, которые могут принимать <tex>N</tex> значений, а поскольку <tex>F</tex> также принимает <tex>N</tex> различных значений при каждом значении аргумента, всего существует <tex>m = N^{N^5}</tex> различных функций <tex>F</tex> (различных моделей).
<br><br>
Автомат фон Неймана имеет <tex>N = 29</tex> различных состояний:<br>
1. Транзитивные состояния (импульсы) <tex>T_{u\alpha\varepsilon}</tex>, где:
::: <tex>
u =
\begin{equation*}
\begin{cases}
0 &\text{—$\;$ обычное состояние,}\\
1 &\text{—$\;$ специальное состояние;}\\
\end{cases}
\end{equation*}
</tex><br>
::: <tex>
\alpha =
\begin{equation*}
\begin{cases}
0 &\text{—$\;$ вправо,}\\
1 &\text{—$\;$ вверх,}\\
2 &\text{—$\;$ влево,}\\
3 &\text{—$\;$ вниз;}\\
\end{cases}
\end{equation*}
</tex><br>
::: <tex>
\varepsilon =
\begin{equation*}
\begin{cases}
0 &\text{—$\;$ состояние покоя,}\\
1 &\text{—$\;$ возбужденное состояние;}\\
\end{cases}
\end{equation*}
</tex><br>
2. Конфлюэнтные состояния <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>
3. Основное состояние <tex>U</tex> (невозбужденное).
<br>
4. Чувствительные (сенситивные) состояния <tex>S_{\Sigma}</tex>, где:
::: <tex>\Sigma = \Theta, 0, 1, 00, 01, 10, 11, 000</tex><br>
и
::: <tex>S_{0000} = T_{000},</tex><br>
::: <tex>S_{0001} = T_{010},</tex><br>
::: <tex>S_{001} = T_{020},</tex><br>
::: <tex>S_{010} = T_{030},</tex><br>
::: <tex>S_{011} = T_{100},</tex><br>
::: <tex>S_{100} = T_{110},</tex><br>
::: <tex>S_{101} = T_{120},</tex><br>
::: <tex>S_{110} = T_{130},</tex><br>
::: <tex>S_{111} = C_{00},</tex><br>
<br>
Основное состояние $U$ может оставаться неизменным или, путем возбуждения, переходить в чувствительное состояние $S$. В последнем случае последнее автоматически пробегает определенную последовательность чувствительных состояний, которая неизбежно заканчивается конфлюэнтным состоянием $C$ или транзитивным состоянием $T$. Оба конечных состояния могут попеременно находиться в возбужденной и невозбужденной форме, оставаться неизменными или переходить снова в основное состояние.<br>
<br>
Более подробно $F$ определяется следующими соотношениями:
# Пусть $n_{\vartheta}^{t - 1} = T_{u\alpha\varepsilon}$:
## $n_{\vartheta}^{t} = U \Leftrightarrow \forall \{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'} \; \wedge \; u \neq u'\} \;\; n_{\vartheta'}^{t - 1} = T_{u'{\alpha}'{\vartheta}'}$;
## $n_{\vartheta}^{t} = T_{u{\alpha}1} \Leftrightarrow$ не выполнено $1.1$ и выполнено одно из следующих:
### $\forall\{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'} \neq -v^\alpha\} \;\; n_{{\vartheta}'}^{t - 1} = T_{u{\alpha}'1}$;
### $\forall\{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{\beta} \neq -v^\alpha, \; \beta = 0,\dots, 3\} \;\; n_{\vartheta}^{t - 1} = C_1$;
## $n_{\vartheta}^{t} = T_{u{\alpha}0}$, иначе.
# Пусть $n_{\vartheta}^{t - 1} = C_{\varepsilon\varepsilon'}$:
## $n_{\vartheta}^{t} = U \Leftrightarrow \forall \{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'}\} \;\; n_{\vartheta'}^{t - 1} = T_{1{\alpha}'1}$;
## $n_{\vartheta}^{t} = C_{\varepsilon'1} \Leftrightarrow$ не выполнено $2.1$ и выполнены следующие условия:
### $\forall\{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'} \} \;\; n_{{\vartheta}'}^{t - 1} = T_{0{\alpha}'1}$;
### Для всех $\{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'} \} \;\; n_{{\vartheta}'}^{t - 1} = T_{0{\alpha}'0}$;
## $n_{\vartheta}^{t} = C_{\varepsilon'0}$, иначе.
# Пусть $n_{\vartheta}^{t - 1} = U$:
## $n_{\vartheta}^{t} = S_0 \Leftrightarrow \forall \{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'}\} \;\; n_{\vartheta'}^{t - 1} = T_{u{\alpha}'1}$;
## $n_{\vartheta}^{t} = U$, иначе.
# Пусть $n_{\vartheta}^{t - 1} = S_\Sigma, \; \Sigma=0,\dots,000$:
## $n_{\vartheta}^{t} = S_{\Sigma1} \Leftrightarrow \forall \{{\vartheta}'\; | \; \vartheta - {\vartheta}' = v^{{\alpha}'}\} \;\; n_{\vartheta'}^{t - 1} = T_{u{\alpha}'1}$;
## $n_{\vartheta}^{t} = S_{\Sigma0}$, иначе.
:::::::::::::::::::::"
=== Принцип работы ===
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.
