Изменения

'''Клеточный автомат'''<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>

'''Окрестность Мура'''<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>

'''Окрестность фон Неймана'''<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>.

'''Классы Вольфрама'''<ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} система классификации классификация клеточных автоматов, основанная на их поведении.

 <gallery mode="packed-hover" widths=3000px heights=400px>Image:Wolfram_classes.jpg|400px|300px|''Классы, предложенные С. Вольфрамом<ref name="skakov">Скаков П.С. Классификация поведения одномерных клеточных автоматов. СПб., 2007 — URL: http://is.ifmo.ru/diploma-theses/_skakov_master.pdf</ref>:''# После некоторого количества шагов система стабилизируется {{---}} все клетки поля переходят в одинаковое состояние;# Состояния могут быть различными, однако клетки в данном случае образуют наборы статичных или периодических простых структур;# Образуются сложные структуры, характер взаимодействия которых во многих случаях выглядит хаотическим;# Сложные структуры, очень сложное, порой непредсказуемое (хаотичное) взаимодействие.</gallery>

<gallery mode="packed-hover" widths=500px heights=250px>Image:Eppstein_classes.jpg|250px|500px|''Классы, предложенные Д. Эпштейном<ref name="skakov" />:''# Автомат предусматривает расширение объектов поля: в клетке не "зарождается жизнь" при наличии одного "живого" соседа;# Автомат не предусматривает расширения объектов поля: в клетке не "зарождается жизнь" при наличии двух</трех "живых" соседей;# Автомат не предусматривает расширения уменьшения объектов поля: клетка не "умирает" от "перенаселения" или "одиночества";# Автоматы, предусматривающие как расширение, так и уменьшение объектов поля.<brgallery>

# Определить все возможные конфигурации состояний окрестности данной ячейки;

# Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с этим правилом правилами переходов на следующей итерации;

Все рассматриваемые автоматы представляют собой Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА ]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге. '''TODO: ADD PICTIRES'''

Некоторые из приведенных далее определений были взяты с этого<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> сайта, а также со смежных с нем страниц.

Дополнительную Основную информацию по игре вы можете найти в статье [[Игра «Жизнь» | "игра «Жизнь»"]]. В данном разделе будут рассмотрены лишь основные типы и примеры конфигураций данной игры.

=== Состояния и правила переходов ===Каждая клетка поля может быть либо белого, либо черного цвета. Белые клетки называются «живыми», черные {{| class="wikitable"|---}} «мертвыми».! scope="col"| Название состояния! scope="col"| Цвет! scope= Правила ==="col"| Переходит в cостояние|-| «Живая клетка»На каждом шаге автомата ко всем клеткам применяются следующие правила:| Белый* В черная клетка| «мертвая клетка», имеющая если имеет ровно три белые соседние клетки, становится белой («зарождается жизнь»);* Если у белой клетки есть две или три белые соседние клетки, то эта клетка сохраняет свой цвет;* Если у белой клетки соседей белого цвета меньше двух или больше трёхтрех соседей в состоянии «живая клетка».|-| «Мертвая клетка»| Черный| «живая клетка», клетка становится черной («умирает от одиночества» или «от перенаселённости»)если имеет ровно трех соседей в состоянии «живая клетка».|}

В зависимости от начального состояния поля, клетки могут образовывать фигуры, обладающие различными свойствами. По этим свойствам принято делить фигуры на следующие классы:* '''Устойчивые фигуры''' {{---}} фигуры, которые остаются неизменными* '''Долгожители''' {{---}} фигуры, которые долго меняются, прежде чем стабилизироваться;* '''Осцилляторы''' {{---}} фигуры, у которых состояние повторяется через некоторое число поколений, большее 1;* '''Двигающиеся фигуры (космические корабли)''' {{---}} фигуры, у которых состояние повторяется, но с некоторым смещением;* '''Ружья''' {{---}} фигуры с повторяющимися состояниями, дополнительно создающие движущиеся фигуры;* '''Паровозы''' {{---}} двигающиеся фигуры с повторяющимися состояниями, которые оставляют за собой другие фигуры в качестве следов;* '''Пожиратели''' {{---}} устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами, уничтожив их;* '''Отражатели''' {{---}} устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;* '''Размножители''' {{---}} конфигурации, количество живых клеток в которых растёт как квадрат количества шагов;Наиболее известные представители данных классов будут рассмотрены далее в статье. ''' TODO: ADD PICTIRESPICTURES'''

Устойчивые фигуры или «натюрморты», делятся на несколько классов<ref>Eric Weisstein. Still Life</ref>:{{Определение|definition=* '''Устойчивый образец''' {{---}} объект, который является собственным родителем;.}}{{Определение|definition=* '''Натюрморт''' <ref>Eric Weisstein. Still Life</ref> {{---}} устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть;.}}{{Определение|definition=* '''Псевдонатюрморт''' {{---}} устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов.}}

'''Ружье''' {{---}} класс конфигураций, у которых основная часть циклически повторяется, как у осцилляторов, а также периодически создаёт космические корабли, которые удаляются от ружья. Данная конфигурация имеет два периода: '''период создания космических кораблей''' и '''период повторения состояний ружья'''.

'''Грабли''' {{---}} паровозы, оставляющие за собой след исключительно из космических кораблей.<br>

=== Состояния и правила переходов ===

! scope="col"| ЗначениеПереходит в состояние

| Клетка, не занятая проводником

| По проводнику могут распространяться электроны«голова электрона», если имеет ровно одного или двух [[#moore_neighborhood | соседей]] в состоянии «голова электрона»

| Проводник, занятый электроном: вместе с «хвостом «хвост электрона» задает направление движения электрона.

| Проводник, занятый электроном: вместе с «головой электрона» задает направление движения электрона.«проводник»

* При одновременном столкновении двух трёх и более "электронов", они исчезают.

В данной статье приведены лишь основные простейшие элементы, которые можно составить в Wireworld.<br>Большое количество примеров приведено в Mirek's Cellebration<ref>"Mirek's Cellebration". URL:http://mirekw.com/ca/index.html</ref> и Zillions of Games<ref>"Zillions of Games". URL:http://zillionsofgames.com</ref>, WireWorld<ref>"WireWorld". URL:http://karl.kiwi.gen.nz/CA-Wireworld.html. </ref>. С ; с помощью элементов Wireworld также был построен<ref>"The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html</ref> компьютер.<br>В данной статье приведены лишь основные простейшие элементы.

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

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

'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<refname="neuman_automata">Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} двумерный клеточный автоматобъект, представляющий собой поле, в каждой клетке поля которого находится конечный автомат с 29 состояниями, каждая клетка имеет 4 соседей, информация приходит с задержкой по крайней мере на 1 единицу времени.

Из 29 состояний одно является невозбудимым, 20 относятся к возбудимым, 8 – к чувствительным.<br>На бесконечном поле задается исходный конечный набор клеток, имеющих не невозбудимое состояние, затем клеточная система начинает работать по правилам переходов. Логическая структура бесконечного клеточного автомата такова, что через некоторый промежуток времени в некоторой области клеточного пространства, отличной от начального условия, появляется копия начального автомата. От дискретной клеточной модели самовоспроизведения фон Нейман собирался перейти к непрерывной модели, которая представляла бы систему дифференциальных уравнений в частных производных диффузионного типа. К сожалению, он не успел осуществить свой замысел.  === Формальное описание Состояния ===Данное описание взято из §5.3 книги "Физика процессов эволюции"<ref name="physics" />.<br>Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:Как было сказано выше, * [[#neiman_auto neiman_neighborhood | автомат Окрестность фон Неймана]] представляет клеточный автомат: <tex>v^0 = (1, 0) \;\;\; v^1 = (0, у которого каждая клетка может находиться в 29 состояниях. Клеточный автомат состоит из многих однотипных автоматов1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, расположенных в узлах решетки-1)</tex>; выход каждого автомата служит входом для * Клетки, дополняющие окрестность фон Неймана до [[#neiman_neighborhood moore_neighborhood | соседних клетококрестности Мура]].<br>Нумерует клетки радиус-вектор : <tex>\vartheta v^4 = (i1, j1), \; i,j \;\; v^5 = 0(-1, 1) \pm ;\;\; v^6 = (-1, -1) \pm 2;\;\; v^7 = (1, \dots-1)</tex>.<br><br>Состояние клетки $\vartheta$ на $t$-ом шаге: <tex>n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{Определение\vartheta + v^\alpha} \; |definition\; \alpha =Назовем '''ближайшими соседями''' клетки те клетки0, что лежат в ее [[#neiman_neighborhood | окрестности фон Неймана]]; клетки\dots , дополняющие [[#neiman_neighborhood | окрестность фон Неймана]] до [[#moore_neighborhood | окрестность Мура]]3), назовем '''ближними соседями'''.F</tex> {{---}}'''TODO: ADD PICTURES'''функция переходов.<br>

Определим восемь векторов расстоянияСостояния клеток рассматриваемого автомата делятся на $4$ различных класса:<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>FU</tex> (различных моделейневозбужденное).<br><br>Автомат фон Неймана имеет <tex>N = 29</tex> различных состояний:<br>12. Транзитивные состояния (импульсы) <tex>T_{u\alpha\varepsilon}</tex>, где:

0 &\text{—$\;$ обычное состояние,}\\ 1 &\text{—$\;$ специальное состояние;}\\ \end{cases}\end{equation*}</tex><br>::: <tex>\alpha = \begin{equation*} \begin{cases} 0 &\text{—$\;$ вправо,}\\ 1 &\text{—$\;$ вверх,}\\ 2 &\text{—$\;$ влево,}\\ 3 &\text{—$\;$ вниз;}\\

0 &\text{—$\;$ состояние покояпокой,}\\ 1 &\text{—$\;$ возбужденное состояниевозбуждение;}\\

23. Конфлюэнтные состояния <tex>C_{\varepsilon{\varepsilon}'}</tex>, где:

0 &\text{—$\;$ состояние покояпокой,}\\ 1 &\text{—$\;$ возбужденное состояниевозбуждение;}\\

0 &\text{—$\;$ состояние покоя покой на следующем такте,}\\ 1 &\text{—$\;$ возбужденное состояние возбуждение на следующем такте;}\\

3. Основное состояние <tex>U</tex> (невозбужденное).<br>4. Чувствительные (сенситивные) состояния <tex>S_{\Sigma}</tex>$S, где:::: <tex>\Sigma = ; S_0 \Theta, 0, 1, 00, 01, 10, 11;, 000</tex><br>и::: <tex>S_{0000} = T_{00000}\;,</tex><br>::: <tex>S_{0001} = T_{01001}\;,</tex><br>::: <tex>S_{001} = T_{020000}\;, S_1 \;,</tex><br>::: <tex>S_{010} = T_{03010}\;,</tex><br>::: <tex>S_{01111} = T_{100},$.</texbr><br>::: Далее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит<tex>S_{100} ref name= T_{110},<"neuman_automata"/tex>аналогию с системой нейронных связей, аналогичным образом строя автомат.<br>::: <tex>S_{101} = T_{120},</tex><br>::: <tex>S_{110} = T_{130}Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$,</tex><br>::: <tex>S_{111} = C_{00}обозначающий,</tex>с какого направления клетка в данном состоянии будет принимать импульс.<br><br>Основное состояние Работу самих нейронов представляют состояния $UС$ может оставаться неизменным или: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), путем которые для возбуждениянеобходимо раздражать одновременно, переходить то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в чувствительное состояние состоянии $ST_1$, выходные направления которых ориентированы на "нейрон". В последнем случае последнее автоматически пробегает определенную последовательность чувствительных Для экономии количества состоянийвводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.<br><br>По аналогии с нейронными сетями, которая неизбежно заканчивается конфлюэнтным состоянием $C$ или транзитивным состоянием $T$автомат должен иметь возможность "расщеплять" передаваемый сигнал, т.е. обеспечить возможность передачи его нескольким клеткам сразу. Оба конечных Данную функцию выполняют конфлюэнтные состояния могут попеременно находиться в возбужденной , по определению имея несколько "выходов" и невозбужденной форме, оставаться неизменными или переходить снова в основное состояниеодин "вход".<br><br>Более подробно Состояния $S_{\Sigma0}$ и $S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов. === Правила переходов ===Функция переходов $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 - 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}$, иначе во всех остальных случаях.

''' TODO: ADD PICS'''<br>На бесконечном поле задается исходный конечный набор Начальная конфигурация описывается конечным набором клеток, имеющих не невозбудимое состояниенаходящихся в возбудимом или чувствительном состоянии. Затем клеточная система начинает работать по правилам переходов. Логическая структура бесконечного клеточного Правила данного автомата таковаустроены таким образом, что через некоторый промежуток времени некоторое количество шагов на поле появляется копия начальной конфигурации в некоторой области клеточного пространства, отличной отличающейся от начального условиятой, появляется копия начального в которой начальная конфигурация была задана.Более детальное описание механизма работы автомата. От дискретной клеточной модели самовоспроизведения фон Нейман собирался перейти к непрерывной модели, которая представляла бы систему дифференциальных уравнений можно найти в частных производных диффузионного типаглаве 2 книги "Теория самовоспроизводящихся автоматов"<ref name="neuman_automata"/>.

Одним из направлений развития работы фон Неймана стали попытки конструирования Примером более простых самовоспроизводящихся клеточных автоматов. Примером эволюции простого самовоспроизводящегося клеточного автомата {{---}} является автомат Лэнгтона<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>.

 В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.<br>Сигнальная лента несет информацию, необходимую для создания копии автомата.

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

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

<gallery mode="packed" widths=75px heights=200px>Image:langton_start.jpg|''Начальная конфигурация' TODO'Image: ADD PICTURESlangton_copy.jpg|''Порожденная копия после 151 такта''<br/gallery>Когда конца * Увеличение длины ленты достигает сигнал на $1$ достигается путем передачи на ее конец сигнала $70$, то длина ;* Поворот ленты увеличивается влево достигается путем передачи на $1$. Когда в ее конец ленты приходят два сигнала $40$, то лента делает поворот налево. Копия исходного состояния получается ;* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.

= Тюрьмиты Тьюрмиты =

'''Тьюрмит''' <ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.

'''TODO[[Игра «Жизнь»]] эмулируется<ref name="mitin" /> с помощью одного тьюрмита: ADD PICTURES'''он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.<br>Тьюрмиты можно программировать для решения достаточно сложных задач: например, один тьюрмит может анализировать размеченную поверхность В области исследований модели ДНК при моделировании активно используются взаимодействующие и оставлять на ней пометки для другого, который будет вносить в нее изменения. При помощи всего лишь одного тьюрмита можно реализоватьплиточные тьюрмиты<ref name="mitin" /> клеточный автомат «Жизнь»: тьюрмит обегает колонию и в соответствии с заданными правилами рисует следующее поколение.

* [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>