Изменения

'''Клеточный автомат''' <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 по данной классификации.

'''Код Вольфрама''' {{---}} система именования клеточных автоматов (как правило, [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]]), предложенная С. Вольфрамом в 1983 году<ref>Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55: 601–644</ref>.<br> Код основан Данная система основана на наблюдении, что таблица, определяющая новое состояние каждой ячейки в автомате, как функция состояний в его окрестности, может интерпретироваться как число из <tex>k</tex>-цифр в <tex>S</tex>-арной позиционной системе счисления, где <tex>S</tex> {{---}} число состояний, которое может иметь каждая ячейка в автомате, <tex>k = S^{2n + 1}</tex> {{---}} число конфигураций окрестности, а <tex>n</tex> {{---}} радиус окрестности.

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

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

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

Так как <tex>11110_2 = 30_10{30}_{10}</tex>, данное правило называется Правилом 30.

Так как <tex>01101110 _2 1101110_2 = 110_10{110}_{10}</tex>, данное правило называется Правилом 110.<br><br><br><br><br><br><br><br> 

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

==== Двоичный сумматор ====Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор. Его функция заключается в том, что при подаче на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. Нарисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.<gallery mode="packed-hover" widths=200px heights=350px>Image:Binary_summator_wireworld.jpg|''Двоичный сумматор''</gallery> = Самовоспроизводящиеся клеточные автоматы (UNDER CONSTRUCTION) ={{В разработке}}В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"<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 книги "Физика процессов эволюции"Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:* [[#neiman_neighborhood | Окрестность фон Неймана]]: <ref nametex>v^0 ="physics">Эбелинг Вернер(1, 0) \;\;\; v^1 = (0, Энгель Андреас1) \;\;\; v^2 = (-1, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС0) \;\;\; v^3 = (0, 2001. - 328 с.1)</ref>.<brtex>;Как было сказано выше* Клетки, дополняющие окрестность фон Неймана до [[#neiman_auto moore_neighborhood | автомат фон Нейманаокрестности Мура]] представляет клеточный автомат: <tex>v^4 = (1, у которого каждая клетка может находиться в 29 состояниях. Клеточный автомат состоит из многих однотипных автоматов1) \;\;\; v^5 = (-1, 1) \;\;\; v^6 = (-1, расположенных в узлах решетки-1) \;\;\; выход каждого автомата служит входом для [[#neiman_neighborhood | соседних клеток]].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>

<br>{{Определение|definition=Назовем '''ближайшими соседями''' клетки те клетки, что лежат в ее [[#neiman_neighborhood | окрестности фон Неймана]]; клетки, дополняющие [[#neiman_neighborhood | окрестность фон Неймана]] до [[#moore_neighborhood | окрестность Мура]], назовем '''ближними соседями'''.}}'''TODOСостояния клеток рассматриваемого автомата делятся на $4$ различных класса: ADD PICTURES'''<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>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: COMPLETE, ADD PICS'''На бесконечном поле задается исходный конечный набор Начальная конфигурация описывается конечным набором клеток, имеющих не невозбудимое состояние. Затем клеточная система начинает работать по правилам переходовнаходящихся в возбудимом или чувствительном состоянии. Логическая структура бесконечного клеточного Правила данного автомата таковаустроены таким образом, что через некоторый промежуток времени некоторое количество шагов на поле появляется копия начальной конфигурации в некоторой области клеточного пространства, отличной отличающейся от начального условиятой, появляется копия начального в которой начальная конфигурация была задана.Более детальное описание механизма работы автомата. От дискретной клеточной модели самовоспроизведения фон Нейман собирался перейти к непрерывной модели, которая представляла бы систему дифференциальных уравнений можно найти в частных производных диффузионного типаглаве 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" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.

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