436
правок
Изменения
Fon Neuman Automat: formal decription started
= Самовоспроизводящиеся клеточные автоматы (COLLECTING INFORMATION) =
В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов:
# Логическая универсальность.
## Может ли при конструировании автомата автоматом происходить усложнение типа автомата?
## Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату (при надлежащем определении понятия эффективности)?
Тьюринг показал, что предложенный им класс автоматов логически универсален, т. е. автоматы Тьюринга могут выполнить произвольный логический процесс (произвольное вычисление), если их снабдить конечным, но сколь угодно продолжаемым запоминающим механизмом (памятью). Тьюринг показал также, что существует универсальная машина Тьюринга, способная выполнять любые вычисления, тем самым дав утвердительный ответ на первый вопрос.
<br>
Дж. фон Нейман доказал существование автомата, удовлетворяющего всем пяти свойствам, построив две<ref name="mitin">Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf</ref> модели, одна из которых будет описана далее.
== Автомат фон Неймана ==
{{Определение
|id=neiman_auto
|definition=
'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref>Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} двумерный клеточный автомат, в каждой клетке поля которого находится конечный автомат с 29 состояниями, каждая клетка имеет 4 соседей, информация приходит с задержкой по крайней мере на 1 единицу времени.
}}
Из 29 состояний одно является невозбудимым (покой), 20 относятся к возбудимым, 8 – к чувствительным.<br>
На бесконечном поле задается исходный конечный набор клеток, имеющих не невозбудимое состояние, затем клеточная система начинает работать по правилам переходов.
Логическая структура бесконечного клеточного автомата такова, что через некоторый промежуток времени в некоторой области клеточного пространства, отличной от начального условия, появляется копия начального автомата. От дискретной клеточной модели самовоспроизведения фон Нейман собирался перейти к непрерывной модели, которая представляла бы систему дифференциальных уравнений в частных производных диффузионного типа. К сожалению, он не успел осуществить свой замысел.
=== Формальное описание ===
Данное описание взято из книги<ref name="physics">Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, 2001. - 328 с.</ref>.<br>
Как было сказано выше, [[#neiman_auto | автомат фон Неймана]] представляет клеточный автомат, у которого каждая клетка может находиться в 29 состояниях. Клеточный автомат состоит из многих однотипных автоматов, расположенных в узлах решетки; выход каждого автомата служит входом для [[#neiman_neighborhood | соседних клеток]].<br>
Нумерует клетки радиус-вектор <tex>\vartheta = (i, j), \; i,j = 0, \pm 1, \pm 2, \dots</tex>.
<br>
'''TODO: ADD PICTURE'''
<br>
{{Определение
|definition=
Назовем '''ближайшими соседями''' клетки те клетки, что лежат в ее [[#neiman_neighborhood | окрестности фон Неймана]]; клетки, дополняющие [[#neiman_neighborhood | окрестность фон Неймана]] до [[#moore_neighborhood | окрестность Мура]], назовем '''ближними соседями'''.
}}
<br>
Определим восемь векторов расстояния ('''TODO: ADD PICTURE'''):<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><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> различных состояний:
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>
== Автомат Лэнгтона ==
<ref>Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf</ref>
= Тюрьмиты =
