Изменения

'''Клеточный автомат''' <ref>Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=Список_заданий_по_ДМ_2к_2020_весна</ref> представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии.<br><br>

'''Окрестность Мура''' <ref>Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.<br>

'''Окрестность фон Неймана''' <ref>Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/Окрестность_фон_Неймана</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.}} {{Определение|id=edem_def|definition='''Райский сад''' {{---}} конфигурация КА, которая не может появиться в результате «эволюции», потому что не имеет предшественников.}}{{Теорема|id=edem_theorem|about=сада Эдема|statement=Клеточный автомат в евклидовой вселенной является локально инъективным тогда и только тогда, когда он сюръективен.Другими словами, теорема утверждает, что сады Эдема существуют только в тех автоматах, в которых существуют близнецы.|proof=Данная теорема была выдвинута и доказана Эдвардом Муром<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>

ДНа ряд серьезных недостатков классификации С. Эпштейн резко критиковалВольфрама указывал<ref name="eppstein">Eppstein D. Classification of Cellular Automata. http://www.ics.uci.edu/~eppstein/ca/wolfram.html</ref> классификацию СД. Эпштейн. Вольфрама, <br>Один из них состоял в частности, назвал её совершенно несостоятельной из-за невозможности за разумное время проверить принадлежность клеточного автомата к какому-либо классу для большого числа клеточных автоматов.<br>Для решения проблемы В свою очередь он предложил свою классификацию систему классификации двухмерных двоичных клеточных автоматов на основе возможностей порождаемых клеточным автоматом объектов к расширению и уменьшению.  Классы, предложенные Д. Эпштейном<ref name="skakov" />:# Все объекты расширяются: в наборе правил есть правило B1 (клетка переходит в состояние 1, если она имеет ровно одного соседа в состоянии 1);# Нет расширяющихся объектов: в наборе правил нет правил B2 или B3 (клетка переходит в состояние 1, если она имеет ровно двух / трёх соседей в состоянии 1).# Уменьшение невозможно: в наборе правил есть правила S01234 или B23/S0 (клетка сохраняет состояние 1, если у неё есть от нуля до четырех соседей в состоянии 1/клетка переходит в состояние 1 при наличии у неё ровно двух или трёх соседей в состоянии 1 и сохраняет это состояние, если у неё нет соседей в состоянии 1).# Возможны и расширение и уменьшение объектов: все остальные случаи.<br>Однако, данная классификация так же не лишена недостатков, в частности не удовлетворяет поставленным перед ней же требованиям: целью данной классификации является выделение призванную выделять кандидатов в универсальные клеточные автоматы. Эпштейн утверждал, что универсальные клеточные автоматы могут принадлежать только к классу 4, однако, существует<ref name="skakov" /> универсальный клеточный автомат, относящийся к классу 3 по данной классификации.

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

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

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

'''«Жизнь»''' {{---}} клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. За один ход клетки перекрашиваются по определенным правиламСостояние, в зависимости которое перейдет клетка на следующем шаге, зависит от их состояний ее соседей в [[#moore_neighborhood | окрестности Мура]].

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

=== Состояния и правила переходов ===Каждая клетка поля может быть либо белого, либо черного цвета. Белые клетки называются «живыми», черные {{| 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>

Размножители классифицируютсяСуществует несколько видов<ref>Breeder – from Eric Weisstein's Treasure Trove of Life</ref> по размножителей, отличающихся между собой относительной подвижности подвижностью полученных конфигураций. Типы обозначаются кодами из трёх Виды кодируются при сочетаниями трех букв, которые обозначаютописывающие, являются ли первичнаясоответственно, вторичная первичную, вторичную и третичная третичную конфигурации соответственно движущимися (: Д) или неподвижными ({{---}} движущаяся, Н).{{---}} неподвижная:<br>Четыре основных типа:

* ДНД {{---}} паровоз, оставляющий вырабатывающий ружья на своем пути;* ДДН {{---}} грабли, оставляющие вырабатывающий паровозы;* ДДД {{---}} Граблиграбли, оставляющие вырабатывающий грабли, так что нет никаких неподвижных элементов. ==== Райский сад ====[[#edem_theorem | Теорема сада Эдема]] применима к «Жизни», поскольку легко найти две различные конфигурации, которые эволюционируют в следующем поколении в одну и ту же конфигурацию.«Мёртвая вселенная» и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту же конфигурацию, все клетки которой мёртвые.Следовательно, в «Жизни» существуют сады Эдема.

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

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

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

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

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

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

Электрон передвигается Движение "электрона" в "цепи" происходит со скоростью одна клетка за шаг. Если по проводу навстречу идут два электрона, при столкновении они исчезают. следующими закономерностями:* При достижении прохождении электроном разветвления проводов по каждому "цепи", в каждое из новых направлений, кроме исходного, уходит по "электрону. Если к разветвлению одновременно подходит <tex>2</tex> ";* При одновременном столкновении трёх и более "электронов", все они исчезают. * При толщине "провода в <tex>" больше $2</tex> клетки поведение электронов аналогично обычному$, при большей толщине поведение становится хаотичным"электроны" начинают двигаться хаотично.

Большие коллекции функциональных элементов имеются В данной статье приведены лишь основные простейшие элементы, которые можно составить в 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>. Кроме того, на сайте The ; с помощью элементов Wireworld computerтакже был построен<ref>"The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html</ref> приводится пример построения в WireWorld компьютера с определенным набором инструкций и регистров, и реализация алгоритма перечисления простых чисел для этого компьютеракомпьютер.

Данный элемент представляет собой «петлю» из клеток проводникаиспользуется для получения электронов, так как при каждом прохождении разветвления электроном, к которой подсоединен провод – выход движущимся по петле генератора, и изначально содержит один образуется новый электрон. С периодом, равным длине петли, этот электрон достигает точки соединения петли с выходом, и дальше разветвляется на два электрона, один из которых идет по выходу, второй – дальше по петле. Таким образом, этот элемент можно использовать для получения в проводе бесконечного количества Частота появления электронов, следующих один за другим на расстоянии, регулируемом регулируется длиной петли.<br>

Этот функциональный Данный элемент имеет две точки подсоединения к проводам – вход и выходдействует точно так же, и его действие состоит в том, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезаюткак одноименный элемент<ref>Диод. URL: https://ru.wikipedia. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направленииorg/wiki/Диод</ref> электрической цепи.

Каждый из этих элементов имеет по 2 входа Данный элемент действует точно так же, как и выхододноименные логические элементы<ref>Дизъюнкция. Наличие электрона на входе соответствует логическому значению «единица», отсутствие – логическому значению «ноль»URL: https://ru. Электрон на выходе появляется согласно таблице истинности соответствующей логической операцииwikipedia.org/wiki/Дизъюнкция<br/ref>* Так, для элемента '''OR''' электрон на любом из входов, или электроны на обоих входах одновременно дают электрон на выходе<ref>Исключающее «или». URL: https://ru.wikipedia.org/wiki/Исключающее_«или»<br/ref>* Для элемента '''XOR''' электрон на любом из входов дает электрон на выходе, но при одновременной подаче электронов на оба входа они исчезают, и электрон на выходе не создается<ref>NAND (логический элемент). URL: https://ru.wikipedia.org/wiki/Штрих_Шеффера<br/ref>* Элемент '''NAND''' работает как тактовый генератор, и посылает электроны на выход во всех случаях, за исключением случая, когда на оба входа одновременно подаются электроны.<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, 1) \;\;\; v^2 = (-1, у которого каждая клетка может находиться в 29 состояниях. Клеточный автомат состоит из многих однотипных автоматов0) \;\;\; v^3 = (0, расположенных в узлах решетки-1)</tex>; выход каждого автомата служит входом для * Клетки, дополняющие окрестность фон Неймана до [[#neiman_neighborhood moore_neighborhood | соседних клетококрестности Мура]].: <tex>v^4 = (1, 1) \;\;\; v^5 = (-1, 1) \;\;\; v^6 = (-1, -1) \;\;\; v^7 = (1, -1)</tex><br><br>Нумерует Состояние клетки радиус$\vartheta$ на $t$-вектор ом шаге: <tex>n_{t}^{\vartheta } = F(i, j), n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; i,j \alpha = 0, \pm 1dots , \pm 23), \dotsF</tex>{{---}} функция переходов.<br>

{{Определение|definition=Назовем '''ближайшими соседями''' клетки те клетки, что лежат в ее [[#neiman_neighborhood | окрестности фон Неймана]]; клетки, дополняющие [[#neiman_neighborhood | окрестность фон Неймана]] до [[#moore_neighborhood | окрестность Мура]], назовем '''ближними соседями'''.}}'''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>tU</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>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>Когда конца ленты достигает сигнал $70$, то длина ленты увеличивается на $1$. Когда в конец ленты приходят два сигнала $40$, то лента делает поворот налево. Копия исходного состояния получается через $151$ такт времени после запуска автомата.

* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;* Поворот ленты влево достигается путем передачи на ее конец сигнала $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>