1632
правки
Изменения
м
В зависимости от начального состояния поля, клетки могут образовывать фигуры, обладающие различными свойствами. По этим свойствам принято делить фигуры на следующие классы:=== Правило 110 ===* '''Устойчивые фигуры''' {{---}} фигуры, которые остаются неизменнымиОпределение* '''Долгожители''' {{---}} фигуры, которые долго меняются, прежде чем стабилизироваться;|definition=* '''ОсцилляторыПравило 110''' {{---}} фигуры[[Линейный клеточный автомат, у которых состояние повторяется через некоторое число поколений, большее эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1;).<br>Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.* '''Двигающиеся фигуры (космические корабли)''' {{---}} фигуры, у которых состояние повторяется, но с некоторым смещением;* '''Ружья''' {{---}} фигуры с повторяющимися состояниями, дополнительно создающие движущиеся фигуры;[[Файл:Rule110.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 110]]<br>* '''Паровозы''' {{---}} двигающиеся фигуры с повторяющимися состояниями, которые оставляют за собой другие фигуры в качестве следов;Правила перехода для Правила 110:* '''Пожиратели''' {{| class="wikitable" style="text---}} устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами, уничтожив их;align: center"* '''Отражатели''' {{-|--}} устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;* '''Размножители''' {{---}} конфигурации, количество живых ! Текущее состояние трёх соседних клеток в которых растёт как квадрат количества шагов;* '''Дублирующиеся фигуры''' {{--| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-! Новое состояние центральной клетки| 0 || 1|| 1|| 0||1|| 1|| 1|| 0|}} фигуры, которые при столкновении с некоторыми фигурами дублируются;* '''Райский сад''' Так как <tex>1101110_2 = {110}_{---10}} конфигурация, которая не может появиться в результате «эволюции»</tex>, потому что не имеет предшественниковданное правило называется Правилом 110.<br><br><br><br><br><br><br>
Наиболее известные представители данных классов будут рассмотрены далее в статье.
''' TODO: ADD PICTIRES'''
У ружья есть два периода: '''период создания космических кораблей''' и '''период повторения состояний ружья'''.
Паровозы условно делят на чистые и грязные:* Чистый паровоз оставляет след, обладающей легко уловимой на глаз периодичностью;* Грязный — сложный, хаотически выглядящий след. ==== Пожиратели ====
Размножители классифицируютсяСуществует несколько видов<ref>Breeder – from Eric Weisstein's Treasure Trove of Life</ref> по размножителей, отличающихся между собой относительной подвижности подвижностью полученных конфигураций. Типы обозначаются кодами из трёх Виды кодируются при сочетаниями трех букв, которые обозначаютописывающие, являются ли первичнаясоответственно, вторичная первичную, вторичную и третичная третичную конфигурации соответственно движущимися (: Д) или неподвижными ({{---}} движущаяся, Н).{{---}} неподвижная:<br>Четыре основных типа:
Теорема применима к «Жизни», поскольку легко найти две различные конфигурации=== Общие закономерности ===Движение "электрона" в "цепи" происходит со следующими закономерностями:* При прохождении электроном разветвления "цепи", которые эволюционируют в следующем поколении в одну и ту же конфигурацию.каждое из новых направлений уходит по "электрону";«Мёртвая вселенная» * При одновременном столкновении трёх и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту же конфигурациюболее "электронов", все клетки которой мёртвыеони исчезают.Следовательно* При толщине "провода" больше $2$, в «Жизни» существуют сады Эдема"электроны" начинают двигаться хаотично.
Клеточный автомат '''WireworldАвтомат фон Неймана'''(клеточная модель самовоспроизведения<refname="neuman_automata">Трофимов ДНейман Дж., Наумов Лфон. Теория самовоспроизводящихся автоматов. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007М. URL: http://is.ifmo.ru/works/wireworld/Мир, 1971</ref> представляет ) {{---}} объект, представляющий собой синхронный поле, в каждой клетке которого находится конечный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний29 состояниями.
=== Тактовый генератор ===Данный элемент Также интерес представляет собой «петлю» из клеток проводникаМуравей Лэнгтона<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>.{{Определение|definition='''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, следующих один за другим на расстояниипредставляющий собой сигнальную ленту, регулируемом длиной петлизаключенную между двумя стенками.<br> В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.<br>[[Файл:Tact_generator_wireworldСигнальная лента несет информацию, необходимую для создания копии автомата.jpg|100px|300px|thumb|center|Тактовый генератор]]}}
[[File:Binary_summator_wireworld* Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;* Поворот ленты влево достигается путем передачи на ее конец сигнала $40$;* Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.jpg|200px|350px|center|thumb|Двоичный сумматор]]
rollbackEdits.php mass rollback
= Базовые определения =
{{Определение
|definition=
'''Клеточный автомат'''<ref>Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=Список_заданий_по_ДМ_2к_2020_весна</ref> представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии.<br><br>
Множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$.<br>
Изначально все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от $1$ до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$). <br><br>
Правила работы клеточного автомата такие: задано число $d$ и функция $f : Q^{2d+1} \to Q$. За один шаг все клетки меняют состояние по следующему правилу: новое состояние клетки $i$ равно $f(s[i - d], s[i - d + 1], \ldots, s[i + d - 1], s[i + d])$. Если клетка с номером $0$ переходит в состояние $Y$, то автомат допускает слово $x$.
}}
Определение и основные свойства линейного клеточного автомата содержатся в статье [[Линейный клеточный автомат, эквивалентность МТ | "линейный клеточный автомат, эквивалентность МТ"]].
{{Определение
|id=moore_neighborhood
|definition=
'''Окрестность Мура''' <ref>Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура</ref> ячейки — {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.<br>Окрестность Мура порядка <tex>r</tex> — множество клеток, расстояние Чебышёва<ref>Расстояние Чебышёва URL: https://ru.wikipedia.org/wiki/Расстояние_Чебышёва</ref> до которых от данной клетки не превышает <tex>r</tex>.<br>
Окрестность Мура порядка <tex>r</tex> в двумерном случае представляет собой квадрат со стороной <tex>2r + 1</tex><ref>Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html</ref>.
}}
{{Определение
|id=neiman_neighborhood
|definition=
'''Окрестность фон Неймана'''<ref>Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/Окрестность_фон_Неймана</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.
}}
= Игра «Жизнь» Классификация клеточных автоматов === Классификация Вольфрама ==
{{Определение
|definition=
'''«Жизнь»Классы Вольфрама''' <ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. За один ход клетки перекрашиваются по определенным правиламклассификация клеточных автоматов, в зависимости от основанная на их соседей в [[#moore_neighborhood | окрестности Мура]]поведении.
}}
<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>
== Основные элементы Классификация Эпштейна ==В данном разделе используются термины из «Словаря Жизни»На ряд серьезных недостатков классификации С. Вольфрама указывал<refname="eppstein">«Словарь Жизни»Eppstein D. Classification of Cellular Automata. URL:http://beluchwww.ics.uci.ruedu/~eppstein/lifeca/lifelexwolfram.html</lexr_oref> Д. Эпштейн.<br>Один из них состоял в невозможности за разумное время проверить принадлежность клеточного автомата к какому-либо классу для большого числа клеточных автоматов.<br>В свою очередь он предложил систему классификации двухмерных двоичных клеточных автоматов, призванную выделять кандидатов в универсальные клеточные автоматы. <gallery mode="packed-hover" widths=500px heights=250px>Image:Eppstein_classes.jpg|250px|500px|''Классы, предложенные Д.htmЭпштейном<ref name="skakov" />''</gallery>Однако, данная классификация так же имела серьезные проблемы, и, в конечном счете, не удовлетворяла своему назначению.Более подробные описания данных классификаций, а также других наиболее распространенных, можно найти в работе П.С. Скакова<refname="skakov" />. В ней, в том числе, были выделены основные достоинства и недостатки различных классификаций, и предложена новая, являющаяся уточнением и модификацией существующих и решающая многие их проблемы. = Одномерные клеточные автоматы === Коды Вольфрама =={{Определение|definition='''Код Вольфрама''' {{---}} система именования клеточных автоматов (как правило, [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]]), предложенная С. Вольфрамом в 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> {{---}} радиус окрестности.}}В соответствии с определением, код может быть вычислен следующим образом:# Определить все возможные конфигурации окрестности данной ячейки;# Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;# Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации;# Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.<br>Далее в статье будут приведены наиболее известные правила.<br>Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге. === Правило 30 ==={{Определение|definition='''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).}}[[Файл:Rule30.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 30]]<br>Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:<br>{| class="wikitable" align="center" style="text-align:center"|-! Текущее состояние трёх соседних клеток !! 111 !! 110 !! 101 !! 100 !! 011 !! 010 !! 001 !! 000|-! Новое состояние центральной клетки| 0 || 0 || 0 || 1 || 1 || 1 || 1 || 0|}Так как <tex>11110_2 = {30}_{10}</tex>, данное правило называется Правилом 30. === Правило 90 ==={{Определение|definition='''Правило 90''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.}}[[Файл:Rule90.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 90]]<br>Правила перехода для Правила 90:{| class="wikitable" style="text-align: center"|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-! Новое состояние центральной клетки| 0 || 1|| 0|| 1||1|| 0|| 1|| 0|}Так как <tex>1011010_2 = {90}_{10}</tex>, данное правило называется Правилом 90.
<br>
=== Устойчивые фигуры Правило 184 === Устойчивые фигуры или «натюрморты»{{Определение|definition='''Правило 184''' {{---}} [[Линейный клеточный автомат, делятся на несколько классовэквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<refbr>Eric Weisstein}}[[Файл:Rule184. Still Lifepng|thumb|300px|right|Эволюция клеточного автомата по Правилу 184]]</refbr>Правила перехода для Правила 184:* Устойчивый образец {{| class="wikitable" style="text---}} объект, который является собственным родителемalign:center;"* Натюрморт {{|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|--}! Новое состояние центральной клетки| 1 || 0|| 1|| 1||1|| 0|| 0|| 0|} устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть;* Псевдонатюрморт Так как <tex>110111000_2 = {184}_{---10}} устойчивый объект, не являющийся натюрмортом</tex>, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортовданное правило называется Правилом 184.
= Клеточные автоматы на двумерной решетке === Игра «Жизнь» ==Некоторые из приведенных далее определений были взяты с этого<ref>Игра "Жизнь". URL: https://ru.wikipedia.org/wiki/Игра_«Жизнь»</ref> сайта, а также со смежных с нем страниц.{{Определение|definition='''«Жизнь»''' {{---}} клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. Состояние, в которое перейдет клетка на следующем шаге, зависит от состояний ее соседей в [[#moore_neighborhood | окрестности Мура]].}}Основную информацию по игре вы можете найти в статье [[Игра «Жизнь» | "игра «Жизнь»"]]. В данном разделе будут рассмотрены лишь основные типы и примеры конфигураций данной игры. === Состояния и правила переходов ==={| class="wikitable"|-! scope="col"| Название состояния! scope="col"| Цвет! scope="col"| Переходит в cостояние|-| «Живая клетка»| Белый| «мертвая клетка», если имеет ровно меньше двух или больше трех соседей в состоянии «живая клетка».|-| «Мертвая клетка»| Черный| «живая клетка», если имеет ровно трех соседей в состоянии «живая клетка».|} === Основные элементы ===В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm</ref>. ''' TODO: ADD PICTURES''' ==== Устойчивые фигуры ==== {{Определение|definition='''Устойчивый образец''' {{---}} объект, который является собственным родителем.}}{{Определение|definition='''Натюрморт'''<ref>Eric Weisstein. Still Life</ref> {{---}} устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть.}}{{Определение|definition='''Псевдонатюрморт''' {{---}} устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов.}} ==== Долгожители ====
{{Определение
|definition=
}}
==== Осцилляторы ====
{{Определение
|definition=
}}
==== Двигающиеся фигуры ====
{{Определение
|definition=
}}
==== Ружья ====
{{Определение
|definition=
'''Ружье''' {{---}} класс конфигураций, у которых основная часть циклически повторяется, как у осцилляторов, а также периодически создаёт космические корабли, которые удаляются от ружья. Данная конфигурация имеет два периода: '''период создания космических кораблей''' и '''период повторения состояний ружья'''.
}}
==== Паровозы ====
{{Определение
|definition=
{{Определение
|definition=
'''Грабли''' {{---}} паровозы, оставляющие за собой след исключительно из космических кораблей.<br>
}}
{{Определение
|definition=
}}
==== Отражатели ====
{{Определение
|definition=
}}
==== Размножители ====
{{Определение
|definition=
}}
* НДД {{---}} ружьё, вырабатывающее грабли;
* ДНД {{---}} паровоз, оставляющий вырабатывающий ружья на своем пути;* ДДН {{---}} грабли, оставляющие вырабатывающий паровозы;* ДДД {{---}} Граблиграбли, оставляющие вырабатывающий грабли, так что нет никаких неподвижных элементов.
=== Дублирующиеся фигуры === === Райский сад =Wireworld =={{Теорема|about=сада ЭдемаОпределение|statementdefinition=Клеточный автомат в евклидовой вселенной является локально инъективным тогда и только тогда, когда он сюръективен.Другими словами, теорема утверждает, что сады Эдема существуют только в тех автоматах, в которых существуют близнецы.|proof=Данная теорема была выдвинута и доказана Эдвардом Муром'''Wireworld'''<ref>MooreТрофимов Д., EНаумов Л. F. (1962)Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, Machine models of self-reproduction, Proc2007. SympURL: http://is. Applied Mathematics Тifmo. 14: 17–33ru/works/wireworld/</ref>представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний.
}}
=== Состояния и правила переходов ===
{| class="wikitable"
|-
! scope="col"| Название состояния
! scope="col"| Цвет
! 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>
<gallery mode="packed-hover">Image:Tact_generator_wireworld.jpg|100px|300px|''Тактовый генератор''</gallery> ==== Диод ====Данный элемент действует точно так же, как одноименный элемент<ref>Диод. URL: https://ru.wikipedia.org/wiki/Диод</ref> электрической цепи.<br><gallery mode="packed-hover">Image:Diode_wireworld.jpg|100px|300px|''Диод''</gallery> ==== Логические элементы OR, XOR и NAND ====Данный элемент действует точно так же, как и одноименные логические элементы<ref>Дизъюнкция. URL: https://ru.wikipedia.org/wiki/Дизъюнкция</ref><ref>Исключающее «или». URL: https://ru.wikipedia.org/wiki/Исключающее_«или»</ref><ref>NAND (логический элемент). URL: https://ru.wikipedia.org/wiki/Штрих_Шеффера</ref>.<br> <gallery mode="packed" widths=75px heights=200px>Image:OR_wireworld.jpg|''OR''Image:XOR_wireworld.jpg|''XOR''Image:NAND_wireworld.jpg|''NAND''</gallery> = Самовоспроизводящиеся клеточные автоматы =В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"<ref name="physics">Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, 2001. - 328 с.</ref>:<br>«# Логическая универсальность.## При каких условиях определенный класс автоматов логически универсален?## Существует ли логически универсальный автомат?# Конструируемость.## Может ли один автомат быть построен другим автоматом?## Какой класс автоматов может быть построен каким-то автоматом?# Конструктивная универсальность.## Существует ли конструктивно универсальный автомат? (т. е. автомат, способный построить любой автомат)# Самовоспроизведение.## Существует ли самовоспроизводящийся автомат?## Существует ли автомат, который, помимо самовоспроизведения, может решать и другие задачи?# Эволюция.## Может ли при конструировании автомата автоматом происходить усложнение типа автомата?## Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату? (при надлежащем определении понятия эффективности):::::::::::::::::::::::::::::::::::::::::::::::::::::::». В то время, как Тьюринг доказал, что [[Машина Тьюринга|машина Тьюринга]] является логически универсальной, Дж. фон Нейман построил автомат<ref name="mitin">Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf</ref>, удовлетворяющий всем пяти свойствам. Одна из таких моделей будет описана далее. == Автомат фон Неймана = Wireworld =
{{Определение
|id=neiman_auto
|definition=
}}
=== Состояния ===Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:* [[Файл#neiman_neighborhood | Окрестность фон Неймана]]:Wireworld_states_meaning_table.jpg<tex>v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1)</tex>;* Клетки, дополняющие окрестность фон Неймана до [[#moore_neighborhood |500px|700px|thumb|centerокрестности Мура]]: <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(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; |\; \alpha = 0, \dots , 3), F</tex> {{---}} функция переходов.<br><br>Состояния клеток рассматриваемого автомата Wireworld]]делятся на $4$ различных класса:<br>1. Основное состояние <tex>U</tex> (невозбужденное).<br>2. Транзитивные состояния <tex>T_{u\alpha\varepsilon}</tex>, где:::: <tex>u = \begin{equation*} \begin{cases} 0 &\text{—$\;$ обычное,}\\ 1 &\text{—$\;$ специальное;}\\ \end{cases}\end{equation*}</tex><br>::: <tex> \alpha = 0, \dots, 3 </tex> {{---}} выходное направление (вправо, вверх, влево, вниз);::: <tex>\varepsilon = \begin{equation*} \begin{cases} 0 &\text{—$\;$ покой,}\\ 1 &\text{—$\;$ возбуждение;}\\ \end{cases}\end{equation*}</tex><br>3. Конфлюэнтные состояния <tex>C_{\varepsilon{\varepsilon}'}</tex>, где:::: <tex>\varepsilon = \begin{equation*} \begin{cases} 0 &\text{—$\;$ покой,}\\ 1 &\text{—$\;$ возбуждение;}\\ \end{cases}\end{equation*}</tex><br>::: <tex>{\varepsilon}' = \begin{equation*} \begin{cases} 0 &\text{—$\;$ покой на следующем такте,}\\ 1 &\text{—$\;$ возбуждение на следующем такте;}\\ \end{cases}\end{equation*}</tex><br>4. Чувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, S_{10} \;, S_{11}$.<br><br>Далее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит<ref name="neuman_automata"/> аналогию с системой нейронных связей, аналогичным образом строя автомат.<br><br>Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс.<br><br>Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в состоянии $T_1$, выходные направления которых ориентированы на "нейрон". Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.<br><br>По аналогии с нейронными сетями, автомат должен иметь возможность "расщеплять" передаваемый сигнал, т.е. обеспечить возможность передачи его нескольким клеткам сразу. Данную функцию выполняют конфлюэнтные состояния, по определению имея несколько "выходов" и один "вход".<br><br>Состояния $S_{\Sigma0}$ и $S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов. === Правила переходов ===Функция переходов $F$ определяется следующими соотношениями:
# Клетка в состоянии $T_{u\alpha\varepsilon}$ перейдет в состояние:## $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' =v^{{\alpha}'}$ в состоянии $T_{u'{\alpha}'{\vartheta}'}$;## $T_{u{\alpha}1}$, если пункт $1.1$ не выполнен, и среди ее соседей найдется клетка, удовлетворяющая одному из условий:### ${\vartheta}'\; : \; \vartheta - {\vartheta}' = Правила v^{{\alpha}'} \neq -v^\alpha$ в состоянии $T_{u{\alpha}'1}$;### ${\vartheta}'\; : \; \vartheta - {\vartheta}' =v^{\beta} \neq -v^\alpha, \; \beta =0,\dots, 3$ в состоянии $C_1$;На каждом шаге автомата ко всем клеткам применяются следующие правила:# Пустая клетка остается пустой# $T_{u{\alpha}0}$ во всех остальных случаях. # Клетка, находящаяся в состоянии «голова электрона» переходит $C_{\varepsilon\varepsilon'}$ перейдет в состояние «хвост электрона».:## $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{1{\alpha}'1}$;# Клетка# $C_{\varepsilon'1}$, если пункт $2.1$ не выполнен, находящаяся и среди ее соседей найдется клетка ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии «хвост электрона» переходит $T_{0{\alpha}'1}$, а все остальные такие клетки не будут находиться в состояние «проводник»состоянии $T_{0{\alpha}'0}$;## $n_{\vartheta}^{t} = C_{\varepsilon'0}$, иначе.# Клетка, находящаяся в состоянии «проводник» переходит $U$ перейдет в состояние «голова электрона», в том случае:## $S_0$, если среди соседних клеток ровно одна или две находятся ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии «голова электрона». Во $T_{u{\alpha}'1}$;## $U$ во всех остальных случаях «проводник» остается «проводником».<br># Клетка в состоянии $S_\Sigma, \; \Sigma=0,\dots,000$ перейдет в состояние:При применении данных правил используется [[#moore_neighborhood | окрестность Мура]] – считается# $S_{\Sigma1}$, что с даннойклеткой соседствуют все восемь если среди ее непосредственных соседейнайдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$;## $S_{\Sigma0}$, во всех остальных случаях.
== Общие закономерности = Принцип работы ===Электрон передвигается со скоростью одна клетка за шаг. Если по проводу навстречу идут два электронаНачальная конфигурация описывается конечным набором клеток, при столкновении они исчезаютнаходящихся в возбудимом или чувствительном состоянии. При достижении электроном разветвления проводов по каждому из направленийПравила данного автомата устроены таким образом, кроме исходногочто через некоторое количество шагов на поле появляется копия начальной конфигурации в области, уходит по электрону. Если к разветвлению одновременно подходит <tex>2</tex> и более электроновотличающейся от той, все они исчезаютв которой начальная конфигурация была задана. При толщине провода Более детальное описание механизма работы автомата можно найти в <tex>главе 2книги "Теория самовоспроизводящихся автоматов"<ref name="neuman_automata"/tex> клетки поведение электронов аналогично обычному, при большей толщине поведение становится хаотичным.
== Основные элементы Автомат Лэнгтона ==Большие коллекции функциональных элементов имеются в пакетах Mirek's CellebrationПримером более простого самовоспроизводящегося клеточного автомата является автомат Лэнгтона<ref>name="Mirek's Cellebrationmitin". URL:http://mirekw.com/ca/index.html</ref> и Zillions of Games<ref>"Zillions of Games". URL:http://zillionsofgames.com</ref>, а также на сайте WireWorld<refbr>"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 компьютера с определенным набором инструкций и регистров, и реализация алгоритма перечисления простых чисел для этого компьютера.
=== Диод Состояния ===Этот функциональный элемент имеет две точки подсоединения ==== Сигнальные состояния ====Состояния $3-7$ относят к проводам – вход и выход, и его действие состоит в том, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезают. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направлении.классу сигнальных:<br>* $3$ используется при повороте;[[Файл:Diode_wireworld* $5$ и $6$ используются для самовоспроизведения.jpg|100px|300px|thumb|center|Диод]]
=== Логические элементы OR, XOR и NAND = Служебные состояния ====Каждый из этих элементов имеет по Состояния $0-2 входа и выход. Наличие электрона на входе соответствует логическому значению «единица», отсутствие – логическому значению «ноль». Электрон на выходе появляется согласно таблице истинности соответствующей логической операции.<br>$ относят к классу служебных:* Так$0$, для элемента '''OR''' электрон на любом из входов, или электроны на обоих входах одновременно дают электрон на выходе.<br>идущее вслед за сигнальным задает направление распространения сигнала;* Для элемента '''XOR''' электрон на любом из входов дает электрон на выходе, но при одновременной подаче электронов на оба входа они исчезают, и электрон на выходе не создается.<br>$1$ является «несущей лентой» сигнала;* Элемент '''NAND''' работает как тактовый генератор, и посылает электроны на выход во всех случаях, за исключением случая, когда на оба входа одновременно подаются электроны.<br>'''TODO: FIX FORMATTING'''[[File:OR_wireworld.jpg|75px|150px|center|thumb|OR]][[File:XOR_wireworld.jpg|75px|150px|center|thumb|XOR]][[File:NAND_wireworldИз клеток в состоянии $2$ строятся «стенки» автомата.jpg|75px|150px|center|thumb|NAND]]
=== Двоичный сумматор Принцип работы ===Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор<gallery mode="packed" widths=75px heights=200px>Image:langton_start. Его функция заключается в том, что при подаче на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) на выходе появится закодированное таким же образом число – сумма чисел на входахjpg|''Начальная конфигурация''Image:langton_copy. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. Наjpg|''Порожденная копия после 151 такта''рисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.</gallery>
= Муравей Тьюрмиты = {{Определение|definition='''Тьюрмит'''<ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.}}[[Файл:Turmite_Langton_ant.png|thumb|300px|right|Результат работы [https://ru.wikipedia.org/wiki/Муравей_Лэнгтона муравья Лэнгтона ] после 27731 итераций]]Каждая строка программы записывается в следующем виде:<pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre><br>[[Игра «Жизнь»]] эмулируется<ref name="mitin" /> с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.<br>В области исследований модели ДНК при моделировании активно используются взаимодействующие и плиточные тьюрмиты<ref name= "mitin" /> .
= См.также =
* [[Линейный ограниченный автомат]]
* [https://ru.wikipedia.org/wiki/Автомат_фон_Неймана Автомат фон Неймана]
* [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>
= Литература =
