Изменения

В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"<ref name="physics">Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, 2001. - 328 с.</ref>:<br>«

В то время, как Тьюринг показалдоказал, что предложенный им класс автоматов логически универсален, т. е. автоматы [[Машина Тьюринга могут выполнить произвольный логический процесс (произвольное вычисление), если их снабдить конечным, но сколь угодно продолжаемым запоминающим механизмом (памятью). Тьюринг показал также, что существует универсальная |машина Тьюринга]] является логически универсальной, способная выполнять любые вычисления, тем самым дав утвердительный ответ на первый вопрос.<br>Дж. фон Нейман доказал существование автомата, удовлетворяющего всем пяти свойствам, построив двепостроил автомат<ref name="mitin">Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf</ref> модели, одна . Одна из которых таких моделей будет описана далее.

'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref>Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} двумерный клеточный автоматобъект, представляющий собой поле, в каждой клетке поля которого находится конечный автомат с 29 состояниями, каждая клетка имеет 4 соседей, информация приходит с задержкой по крайней мере на 1 единицу времени.}} Из 29 состояний одно является невозбудимым, 20 относятся к возбудимым, 8 – к чувствительным.<br>На бесконечном поле задается исходный конечный набор клеток, имеющих не невозбудимое состояние, затем клеточная система начинает работать по правилам переходов. Логическая структура бесконечного клеточного автомата такова, что через некоторый промежуток времени в некоторой области клеточного пространства, отличной от начального условия, появляется копия начального автомата. От дискретной клеточной модели самовоспроизведения фон Нейман собирался перейти к непрерывной модели, которая представляла бы систему дифференциальных уравнений в частных производных диффузионного типа. К сожалению, он не успел осуществить свой замысел.  === Формальное описание ===Данное описание взято из §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 | окрестность Мура]], назовем '''ближними соседями'''.

В соотношении выше <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>== Состояния и правила переходов ===

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>U<br/tex>(невозбужденное);3. Основное состояние # Чувствительные (сенситивные) состояния <tex>US_{\Sigma}</tex> (невозбужденное).

4. Чувствительные (сенситивные) состояния <tex>S_{\Sigma}</tex>, где''' TODO:::: <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>ADD SCHEME'''

Основное состояние Переход из $U$ может оставаться неизменным или, путем возбуждения, переходить в чувствительное состояние $S$. В последнем случае последнее автоматически пробегает определенную последовательность чувствительных осуществляется путем возбуждения, после которого автомат проходит ряд сенситивных состояний, которая неизбежно заканчивается конфлюэнтным состоянием в конечном счете, переходя в состояние $C$ или транзитивным состоянием $T$. Оба конечных состояния могут попеременно находиться в возбужденной и невозбужденной форме, оставаться неизменными или переходить снова в основное состояние$U$.<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состояния и правила перехода данного автомата описаны в §5.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} книги "Физика процессов эволюции"<ref name= S_{\Sigma0}$, иначе"physics" />.

На бесконечном поле задается исходный конечный набор Начальная конфигурация описывается конечным набором клеток, имеющих не невозбудимое состояние. Затем клеточная система начинает работать по правилам переходовнаходящихся в возбудимом или чувствительном состоянии. Логическая структура бесконечного клеточного Правила данного автомата таковаустроены таким образом, что через некоторый промежуток времени некоторое количество шагов на поле появляется копия начальной конфигурации в некоторой области клеточного пространства, отличной отличающейся от начального условия, появляется копия начального автомата. От дискретной клеточной модели самовоспроизведения фон Нейман собирался перейти к непрерывной моделитой, которая представляла бы систему дифференциальных уравнений в частных производных диффузионного типакоторой начальная конфигурация была задана.

Одним из направлений развития работы фон Неймана стали попытки конструирования Примером более простых самовоспроизводящихся клеточных автоматов. Примером эволюции простого самовоспроизводящегося клеточного автомата {{---}} является автомат Лэнгтона<ref name="mitin" />.<br> В статье<ref>Byl John. Self-reproduction in small cellular automata. Physica D, v. 34 (1989),p.295-299.</ref> приводятся самовоспроизводящиеся автоматы, которые еще проще автоматов Лэнгтона, показанных на '''изображениях выше'''. Оказалось, что можно сконструировать самовоспроизводящийся автомат всего лишь из 10 клеток, при этом каждая клетка автомата может находиться в одном из шести возможных состояний.<br>

Также интерес представляет Муравей Лэнгтона<ref>Langton, Chris G. (1986). "Studying artificial life with cellular automata", 120–149</ref>, разработанный в 1986 году Крисом Лэнгтоном. Данный автомат являетсяи являющимся, по сути, двумерной машиной Тьюринга с 2 символами и 4 состояниями<ref>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.</ref>.

==== Сигнальные состояния ====Состояния $3-7$ относят к классу сигнальных:* $0,\;1,\;23$ {{---}} служебные состоянияиспользуется при повороте;* $3,\;4,\;5,\;$ и $6,\;7$ {{---}} сигнальные состоянияиспользуются для самовоспроизведения.

Из клеток в состоянии ==== Служебные состояния ====Состояния $0-2$ строятся «стенки» автомата.относят к классу служебных:Состояние * $10$ является «несущей частотой», или, скорее, «несущей лентой» сигнала.Вслед идущее вслед за сигнальным состоянием должно идти состояние $0$ {{---}} так задается задает направление распространения сигнала.;Состояние * $31$ используется является «несущей лентой» сигнала;* Из клеток в качестве промежуточного состояния при повороте, состояния состоянии $52$ и $6$ используются при отделении дочернего строятся «стенки» автомата и для инициализации новой итерации самовоспроизведения.

Когда конца * Увеличение длины ленты достигает сигнал на $1$ достигается путем передачи на ее конец сигнала $70$, то длина ;* Поворот ленты увеличивается влево достигается путем передачи на $1$. Когда в ее конец ленты приходят два сигнала $40$, то лента делает поворот налево. Копия исходного состояния получается ;* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.