Изменения

Перейти к: навигация, поиск

Модели клеточных автоматов

15 050 байт убрано, 19:13, 4 сентября 2022
м
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>
|id=moore_neighborhood
|definition=
'''Окрестность Мура''' <ref>Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура</ref> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.<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> ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.}} {{Определение|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>.
}}
{{Определение
|definition=
'''Классы Вольфрама'''<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 по данной классификации.
<gallery mode="packed-hover" widths=500px heights=250px>
Image:Eppstein_classes.jpg|250px|500px|''Классы, предложенные Д. Эпштейном<ref name="skakov" />''
</gallery>
Однако, данная классификация так же имела серьезные проблемы, и, в конечном счете, не удовлетворяла своему назначению.
Более подробные описания данных классификаций, а также других наиболее распространенных, можно найти в работе П.С. Скакова<ref name="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>Во всех случаях рассматриваются [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя возможными состояниями. Каждая из клеток имеет начальное состояние. В дискретные моменты времени каждая клетка изменяет своё состояние, причем оно зависит в зависимости от предыдущего состояния этой ячейки ее ближайших соседей и предыдущего ее состояния двух соседних ячеекна предыдущем шаге'''TODO: ADD PICTIRES'''
=== Правило 30 ===
'''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).
}}
[[Файл:Rule30.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 30]]
<br>
Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:<br>
{| class="wikitable" align="center" style="text-align:center"
| 0 || 0 || 0 || 1 || 1 || 1 || 1 || 0
|}
Так как <tex>11110_2 = 30_10{30}_{10}</tex>, данное правило называется Правилом 30.
=== Правило 90 ===
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
}}
[[Файл:Rule90.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 90]]
<br>
Правила перехода для Правила 90:
{| class="wikitable" style="text-align: center"
| 0 || 1|| 0|| 1||1|| 0|| 1|| 0
|}
Так как <tex>1011010_2 = {90}_{10}</tex>, данное правило называется Правилом 90.
=== Правило 110 ===
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
}}
[[Файл:Rule110.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 110]]
<br>
Правила перехода для Правила 110:
{| class="wikitable" style="text-align: center"
| 0 || 1|| 1|| 0||1|| 1|| 1|| 0
|}
Так как <tex>01101110 _2 1101110_2 = 110_10{110}_{10}</tex>, данное правило называется Правилом 110.<br><br><br><br><br><br><br><br> 
=== Правило 184 ===
'''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>
}}
[[Файл:Rule184.png|thumb|300px|right|Эволюция клеточного автомата по Правилу 184]]
<br>
Правила перехода для Правила 184:
{| class="wikitable" style="text-align:center;"
| 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>.
В зависимости от начального состояния поля, клетки могут образовывать фигуры, обладающие различными свойствами. По этим свойствам принято делить фигуры на следующие классы:* '''Устойчивые фигуры''' {{---}} фигуры, которые остаются неизменными* '''Долгожители''' {{---}} фигуры, которые долго меняются, прежде чем стабилизироваться;* '''Осцилляторы''' {{---}} фигуры, у которых состояние повторяется через некоторое число поколений, большее 1;* '''Двигающиеся фигуры (космические корабли)''' {{---}} фигуры, у которых состояние повторяется, но с некоторым смещением;* '''Ружья''' {{---}} фигуры с повторяющимися состояниями, дополнительно создающие движущиеся фигуры;* '''Паровозы''' {{---}} двигающиеся фигуры с повторяющимися состояниями, которые оставляют за собой другие фигуры в качестве следов;* '''Пожиратели''' {{---}} устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами, уничтожив их;* '''Отражатели''' {{---}} устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;* '''Размножители''' {{---}} конфигурации, количество живых клеток в которых растёт как квадрат количества шагов;Наиболее известные представители данных классов будут рассмотрены далее в статье. ''' TODO: ADD PICTIRESPICTURES'''
==== Устойчивые фигуры ====
Устойчивые фигуры или «натюрморты», делятся на несколько классов<ref>Eric Weisstein. Still Life</ref>:{{Определение|definition=* '''Устойчивый образец''' {{---}} объект, который является собственным родителем;.}}{{Определение|definition=* '''Натюрморт''' <ref>Eric Weisstein. Still Life</ref> {{---}} устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть;.}}{{Определение|definition=* '''Псевдонатюрморт''' {{---}} устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов.}}
==== Долгожители ====
{{Определение
|definition=
'''Ружье''' {{---}} класс конфигураций, у которых основная часть циклически повторяется, как у осцилляторов, а также периодически создаёт космические корабли, которые удаляются от ружья. Данная конфигурация имеет два периода: '''период создания космических кораблей''' и '''период повторения состояний ружья'''.
}}
У ружья есть два периода: '''период создания космических кораблей''' и '''период повторения состояний ружья'''.
==== Паровозы ====
{{Определение
|definition=
'''Грабли''' {{---}} паровозы, оставляющие за собой след исключительно из космических кораблей.<br>
}}
Паровозы условно делят на чистые и грязные:
* Чистый паровоз оставляет след, обладающей легко уловимой на глаз периодичностью;
* Грязный — сложный, хаотически выглядящий след.
==== Пожиратели ====
}}
Размножители классифицируютсяСуществует несколько видов<ref>Breeder – from Eric Weisstein's Treasure Trove of Life</ref> по размножителей, отличающихся между собой относительной подвижности подвижностью полученных конфигураций. Типы обозначаются кодами из трёх Виды кодируются при сочетаниями трех букв, которые обозначаютописывающие, являются ли первичнаясоответственно, вторичная первичную, вторичную и третичная третичную конфигурации соответственно движущимися (: Д) или неподвижными ({{---}} движущаяся, Н).{{---}} неподвижная:<br>Четыре основных типа:
* НДД {{---}} ружьё, вырабатывающее грабли;
* ДНД {{---}} паровоз, оставляющий вырабатывающий ружья на своем пути;* ДДН {{---}} грабли, оставляющие вырабатывающий паровозы;* ДДД {{---}} Граблиграбли, оставляющие вырабатывающий грабли, так что нет никаких неподвижных элементов. ==== Райский сад ====[[#edem_theorem | Теорема]] применима к «Жизни», поскольку легко найти две различные конфигурации, которые эволюционируют в следующем поколении в одну и ту же конфигурацию.«Мёртвая вселенная» и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту же конфигурацию, все клетки которой мёртвые.Следовательно, в «Жизни» существуют сады Эдема.
== Wireworld ==
Клеточный автомат '''Wireworld'''<ref>Трофимов Д., Наумов Л. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007. URL: http://is.ifmo.ru/works/wireworld/</ref> представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний.
}}
=== Состояния и правила переходов ===
{| class="wikitable"
|-
! scope="col"| Название состояния
! scope="col"| Цвет
! scope="col"| ЗначениеПереходит в состояние
|-
| Пустая клетка
| Черный
| Клетка, не занятая проводником
|-
| Проводник
| Желтый
| По проводнику могут распространяться электроны«голова электрона», если имеет ровно одного или двух [[#moore_neighborhood | соседей]] в состоянии «голова электрона»
|-
| Голова электрона
| Красный
| Проводник, занятый электроном: вместе с «хвостом «хвост электрона» задает направление движения электрона.
|-
| Хвост электрона
| Синий
| Проводник, занятый электроном: вместе с «головой электрона» задает направление движения электрона.«проводник»
|}
 
=== Правила ===
На каждом шаге автомата ко всем клеткам применяются следующие правила:
# Пустая клетка остается пустой.
# Клетка, находящаяся в состоянии «голова электрона» переходит в состояние «хвост электрона».
# Клетка, находящаяся в состоянии «хвост электрона» переходит в состояние «проводник».
# Клетка, находящаяся в состоянии «проводник» переходит в состояние «голова электрона», в том случае, если среди соседних клеток ровно одна или две находятся в состоянии «голова электрона». Во всех остальных случаях «проводник» остается «проводником».<br>
При применении данных правил используется [[#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>
<gallery mode="packed-hover">
==== Диод ====
Этот функциональный Данный элемент имеет две точки подсоединения к проводам – вход и выходдействует точно так же, и его действие состоит в том, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезаюткак одноименный элемент<ref>Диод. URL: https://ru.wikipedia. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направленииorg/wiki/Диод</ref> электрической цепи.
<br>
<gallery mode="packed-hover">
==== Логические элементы OR, XOR и NAND ====
Каждый из этих элементов имеет по 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>
<gallery mode="packed" widths=75px heights=200px>
Image:XOR_wireworld.jpg|''XOR''
Image:NAND_wireworld.jpg|''NAND''
</gallery>
 
==== Двоичный сумматор ====
Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор. Его функция заключается в том, что при подаче на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. На
рисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.
<gallery mode="packed-hover" widths=200px heights=350px>
Image:Binary_summator_wireworld.jpg|''Двоичный сумматор''
</gallery>
= Самовоспроизводящиеся клеточные автоматы =
{{В разработке}}В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"<ref name="physics">Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.:Эдиториал УРСС, 2001. - 328 с.</ref>:<br>«
# Логическая универсальность.
## При каких условиях определенный класс автоматов логически универсален?
## Какой класс автоматов может быть построен каким-то автоматом?
# Конструктивная универсальность.
## Существует ли конструктивно универсальный автомат ? (т. е. автомат, способный построить любой автомат)?
# Самовоспроизведение.
## Существует ли самовоспроизводящийся автомат?
## Существует ли автомат, который , помимо самовоспроизведения , может решать и другие задачи?
# Эволюция.
## Может ли при конструировании автомата автоматом происходить усложнение типа автомата?
## Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату ? (при надлежащем определении понятия эффективности)?:::::::::::::::::::::::::::::::::::::::::::::::::::::::».
В то время, как Тьюринг показалдоказал, что предложенный им класс автоматов логически универсален, т. е. автоматы [[Машина Тьюринга могут выполнить произвольный логический процесс (произвольное вычисление), если их снабдить конечным, но сколь угодно продолжаемым запоминающим механизмом (памятью). Тьюринг показал также, что существует универсальная |машина Тьюринга]] является логически универсальной, способная выполнять любые вычисления, тем самым дав утвердительный ответ на первый вопрос.<br>Дж. фон Нейман доказал существование автомата, удовлетворяющего всем пяти свойствам, построив двепостроил автомат<ref name="mitin">Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf</ref> модели, одна удовлетворяющий всем пяти свойствам. Одна из которых таких моделей будет описана далее.
== Автомат фон Неймана ==
|id=neiman_auto
|definition=
'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<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>
<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>, где:
::: <tex>
u =
\begin{equation*}
\begin{cases}
0 &\text{—$\;$ обычное состояние,}\\ 1 &\text{—$\;$ специальное состояние;}\\ \end{cases}\end{equation*}</tex><br>::: <tex>\alpha = \begin{equation*} \begin{cases} 0 &\text{—$\;$ вправо,}\\ 1 &\text{—$\;$ вверх,}\\ 2 &\text{—$\;$ влево,}\\ 3 &\text{—$\;$ вниз;}\\
\end{cases}
\end{equation*}
</tex><br>
::: <tex> \alpha = 0, \dots, 3 </tex> {{---}} выходное направление (вправо, вверх, влево, вниз);
::: <tex>
\varepsilon =
\begin{equation*}
\begin{cases}
0 &\text{—$\;$ состояние покояпокой,}\\ 1 &\text{—$\;$ возбужденное состояниевозбуждение;}\\
\end{cases}
\end{equation*}
</tex><br>
23. Конфлюэнтные состояния <tex>C_{\varepsilon{\varepsilon}'}</tex>, где:
::: <tex>
\varepsilon =
\begin{equation*}
\begin{cases}
0 &\text{—$\;$ состояние покояпокой,}\\ 1 &\text{—$\;$ возбужденное состояниевозбуждение;}\\
\end{cases}
\end{equation*}
\begin{equation*}
\begin{cases}
0 &\text{—$\;$ состояние покоя покой на следующем такте,}\\ 1 &\text{—$\;$ возбужденное состояние возбуждение на следующем такте;}\\
\end{cases}
\end{equation*}
</tex><br>
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} = C_{\varepsilon'0}$, иначе.
# Пусть Клетка в состоянии $n_{\vartheta}^{t - 1} = U$перейдет в состояние:## $n_{\vartheta}^{t} = S_0 \Leftrightarrow \forall \{$, если среди ее соседей найдется ${\vartheta}'\; | : \; \vartheta - {\vartheta}' = v^{{\alpha}'}\} \;\; n_{\vartheta'}^{t - 1} = $ в состоянии $T_{u{\alpha}'1}$;## $n_{\vartheta}^{t} = U$, иначево всех остальных случаях.# Пусть Клетка в состоянии $n_{\vartheta}^{t - 1} = S_\Sigma, \; \Sigma=0,\dots,000$перейдет в состояние:## $n_{\vartheta}^{t} = S_{\Sigma1} \Leftrightarrow \forall \{$, если среди ее соседей найдется ${\vartheta}'\; | : \; \vartheta - {\vartheta}' = v^{{\alpha}'}\} \;\; n_{\vartheta'}^{t - 1} = $ в состоянии $T_{u{\alpha}'1}$;## $n_{\vartheta}^{t} = 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>.
{{Определение
|definition=
'''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками.<br>
 В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.<br>Сигнальная лента несет информацию, необходимую для создания копии автомата.
}}
Сигнальная лента несет информацию, необходимую для создания копии автомата.<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$ такт времени после запуска автомата. = Тюрьмиты Тьюрмиты =
{{Определение
|definition=
'''Тьюрмит''' <ref name="mitin" /> {{---}} это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.
}}
[[Файл:Turmite_Langton_ant.png|thumb|300px|right|Результат работы [https://ru.wikipedia.org/wiki/Муравей_Лэнгтона муравья Лэнгтона] после 27731 итераций]]
Каждая строка программы записывается в следующем виде:
<pre><текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние></pre>
<br>
'''TODO[[Игра «Жизнь»]] эмулируется<ref name="mitin" /> с помощью одного тьюрмита: ADD PICTURES'''он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.<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>
= Литература =
1632
правки

Навигация