436
правок
Изменения
Refactor
}}
{{Определение
|id=moore_neighborhoodneiman_neighborhood
|definition=
'''Окрестность фон Неймана''' ячейки {{---}} совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.
}}
{{Определение|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>.}} = Классификация клеточных автоматов ='''TODO: EXPLAIN CONFIGURATIONS' NATURE'''== Классификация Вольфрама =={{Определение|definition='''Классы Вольфрама'''<ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} система классификации клеточных автоматов, основанная на их поведении.}}Классы, предложенные С. Вольфрамом<ref name="skakov">Скаков П.С. Классификация поведения одномерных клеточных автоматов. СПб., 2007 — URL: http://is.ifmo.ru/diploma-theses/_skakov_master.pdf</ref>:# Эволюция системы заканчивается переходом всех клеток поля в одинаковое состояние;# Существует много конечных состояний, но все они состоят из набора простых структур, которые остаются неизменными или повторяются через некоторое небольшое число шагов;# Поведение сложное, во многих отношениях выглядит хаотическим;# Смесь хаоса и порядка: порождаются локальные структуры, которые перемещаются и взаимодействуют друг с другом очень сложным образом.Отнесение конкретного клеточного автомата к какому-либо из классов затруднено, так как не указано, при каких начальных условиях ожидается указанное выше поведение. Предполагается, что класс следует выбирать по самому сложному поведению, которое удастся получить. <br><br>В работе П.С. Скакова<ref name="skakov" /> была предложена новая классификация, являющаяся уточнением и модификацией классификации Вольфрама, проведённой с целью уменьшения сложности определения класса. == Классификация Эпштейна ==Классы, предложенные Д. Эпштейном<ref name="skakov" />:# Все объекты расширяются: в наборе правил есть правило B1 (клетка переходит в состояние 1, если она имеет ровно одного соседа в состоянии 1);# Нет расширяющихся объектов: в наборе правил нет правил B2 или B3 (клетка переходит в состояние 1, если она имеет ровно двух / трёх соседей в состоянии 1).# Уменьшение невозможно: в наборе правил есть правила S01234 или B23/S0 (клетка сохраняет состояние 1, если у неё есть от нуля до четырех соседей в состоянии 1/клетка переходит в состояние 1 при наличии у неё ровно двух или трёх соседей в состоянии 1 и сохраняет это состояние, если у неё нет соседей в состоянии 1).# Возможны и расширение и уменьшение объектов: все остальные случаи. = Одномерные клеточные автоматы === Коды Вольфрама =={{Определение|definition='''Код Вольфрама''' {{---}} система именования клеточных автоматов (как правило, [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]]), предложенная С. Вольфрамом в 1983 году<ref>Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55: 601–644</ref>. Код основан на наблюдении, что таблица, определяющая новое состояние каждой ячейки в автомате, как функция состояний в его окрестности, может интерпретироваться как число из <tex>k</tex>-цифр в <tex>S</tex>-арной позиционной системе счисления, где <tex>S</tex> {{---}} число состояний, которое может иметь каждая ячейка в автомате, <tex>k = S^{2n + 1}</tex> {{---}} число конфигураций окрестности, а <tex>n</tex> {{---}} радиус окрестности.}}В соответствии с определением, код может быть вычислен следующим образом:# Определить все возможные конфигурации состояний окрестности данной ячейки;# Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;# Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с этим правилом на следующей итерации;# Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама. Далее в статье будут приведены наиболее известные правила. Рассматривается бесконечный одномерный массив ячеек клеточного автомата с двумя возможными состояниями. Каждая из клеток имеет начальное состояние. В дискретные моменты времени каждая клетка изменяет своё состояние, причем оно зависит от предыдущего состояния этой ячейки и предыдущего состояния двух соседних ячеек. '''TODO: ADD PICTIRES''' === Правило 30 ==={{Определение|definition='''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).}}Для Правила 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 её двух соседей.}}Правила перехода для Правила 90:{| class="wikitable" style="text-align: center"|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-! Новое состояние центральной клетки| 0 || 1|| 0|| 1||1|| 0|| 1|| 0|} === Правило 110 ==={{Определение|definition='''Правило 110''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.}}Правила перехода для Правила 110:{| class="wikitable" style="text-align: center"|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-! Новое состояние центральной клетки| 0 || 1|| 1|| 0||1|| 1|| 1|| 0|}Так как <tex>01101110 _2 = 110_10</tex>, данное правило называется Правилом 110. === Правило 184 ==={{Определение|definition='''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>}}Правила перехода для Правила 184:{| class="wikitable" style="text-align:center;"|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-! Новое состояние центральной клетки| 1 || 0|| 1|| 1||1|| 0|| 0|| 0|} = Клеточные автоматы на двумерной решетке === Игра «Жизнь» ==
{{Определение
|definition=
'''«Жизнь»''' {{---}} клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. За один ход клетки перекрашиваются по определенным правилам, в зависимости от их соседей в [[#moore_neighborhood | окрестности Мура]].
}}
=== Состояния ===
Каждая клетка поля может быть либо белого, либо черного цвета. Белые клетки называются «живыми», черные {{---}} «мертвыми».
=== Правила ===
На каждом шаге автомата ко всем клеткам применяются следующие правила:
* В черная клетка, имеющая ровно три белые соседние клетки, становится белой («зарождается жизнь»);
* Если у белой клетки соседей белого цвета меньше двух или больше трёх, клетка становится черной («умирает от одиночества» или «от перенаселённости»).
=== Основные элементы ===
В данном разделе используются термины из «Словаря Жизни»<ref>«Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm</ref>.
* '''Отражатели''' {{---}} устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;
* '''Размножители''' {{---}} конфигурации, количество живых клеток в которых растёт как квадрат количества шагов;
Наиболее известные представители данных классов будут рассмотрены далее в статье.
''' TODO: ADD PICTIRES'''
==== Устойчивые фигуры ====
Устойчивые фигуры или «натюрморты», делятся на несколько классов<ref>Eric Weisstein. Still Life</ref>:
* '''Устойчивый образец''' {{---}} объект, который является собственным родителем;
* '''Псевдонатюрморт''' {{---}} устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов.
==== Долгожители ====
{{Определение
|definition=
}}
==== Осцилляторы ====
{{Определение
|definition=
}}
==== Двигающиеся фигуры ====
{{Определение
|definition=
}}
==== Ружья ====
{{Определение
|definition=
У ружья есть два периода: '''период создания космических кораблей''' и '''период повторения состояний ружья'''.
==== Паровозы ====
{{Определение
|definition=
'''Грабли''' {{---}} паровозы, оставляющие за собой след исключительно из космических кораблей.
}}
Паровозы условно делят на чистые и грязные:
* Чистый паровоз оставляет след, обладающей легко уловимой на глаз периодичностью;
* Грязный — сложный, хаотически выглядящий след.
==== Пожиратели ====
{{Определение
|definition=
}}
==== Отражатели ====
{{Определение
|definition=
}}
==== Размножители ====
{{Определение
|definition=
* ДДД {{---}} Грабли, оставляющие грабли, так что нет никаких неподвижных элементов.
=== Дублирующиеся фигуры === === Райский сад ==={{Теорема|about=сада Эдема|statement=Клеточный автомат в евклидовой вселенной является локально инъективным тогда и только тогда, когда он сюръективен.Другими словами, теорема утверждает, что сады Эдема существуют только в тех автоматах, в которых существуют близнецы.[[#edem_theorem |proof=Данная теорема была выдвинута и доказана Эдвардом Муром<ref>Moore, E. F. (1962), Machine models of self-reproduction, Proc. Symp. Applied Mathematics Т. 14: 17–33</ref>.}} Теорема ]] применима к «Жизни», поскольку легко найти две различные конфигурации, которые эволюционируют в следующем поколении в одну и ту же конфигурацию.
«Мёртвая вселенная» и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту же конфигурацию, все клетки которой мёртвые.
Следовательно, в «Жизни» существуют сады Эдема.
= Автомат фон Неймана (NOT STARTED) = = Автомат Ооно–Кохомото (NOT STARTED) ='''TODO: WRITE THE ARTICLE'''Смотреть в статье<ref>Лобанов А.И. Модели клеточных автоматов // Компьютерные исследования и моделирование, 2010, т. 2, № 3, с. 273-293</ref>. = Классификация Вольфрама и коды Вольфрама ={{Определение|definition='''Классы Вольфрама'''<ref>Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8</ref> {{---}} система классификации клеточных автоматов, основанная на их поведении.}}Классы, предложенные С. Вольфрамом:# Эволюция системы заканчивается переходом всех клеток поля в одинаковое состояние;# Существует много конечных состояний, но все они состоят из набора простых структур, которые остаются неизменными или повторяются через некоторое небольшое число шагов;# Поведение сложное, во многих отношениях выглядит хаотическим;# Смесь хаоса и порядка: порождаются локальные структуры, которые перемещаются и взаимодействуют друг с другом очень сложным образом.Отнесение конкретного клеточного автомата к какому-либо из классов затруднено, так как не указано, при каких начальных условиях ожидается указанное выше поведение. Предполагается, что класс следует выбирать по самому сложному поведению, которое удастся получить. <br><br>В работе П.С. Скакова<ref>Скаков П.С. Классификация поведения одномерных клеточных автоматов. СПб., 2007 — URL: http://is.ifmo.ru/diploma-theses/_skakov_master.pdf</ref> была предложена новая классификация, являющаяся уточнением и модификацией классификации Вольфрама, проведённой с целью уменьшения сложности определения класса.<br><br>{{Определение|definition='''Код Вольфрама''' {{---}} система именования клеточных автоматов (как правило, [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]]), предложенная С. Вольфрамом в 1983 году<ref>Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55: 601–644</ref>. Код основан на наблюдении, что таблица, определяющая новое состояние каждой ячейки в автомате, как функция состояний в его окрестности, может интерпретироваться как число из <tex>k</tex>-цифр в <tex>S</tex>-арной позиционной системе счисления, где <tex>S</tex> {{---}} число состояний, которое может иметь каждая ячейка в автомате, <tex>k = S^{2n + 1}</tex> {{---}} число конфигураций окрестности, а <tex>n</tex> {{---}} радиус окрестности.}}В соответствии с определением, код может быть вычислен следующим образом:# Определить все возможные конфигурации состояний окрестности данной ячейки;# Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;# Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с этим правилом на следующей итерации;# Интерпретируя полученный список состояний как <tex>S</tex>-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама. Далее в статье будут приведены наиболее известные правила. Рассматривается бесконечный одномерный массив ячеек клеточного автомата с двумя возможными состояниями. Каждая из клеток имеет начальное состояние. В дискретные моменты времени каждая клетка изменяет своё состояние, причем оно зависит от предыдущего состояния этой ячейки и предыдущего состояния двух соседних ячеек. TODO: ADD PICTIRES == Правило 30 =={{Определение|definition='''Правило 30''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).}}Для Правила 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 её двух соседей.}}Правила перехода для Правила 90:{| class="wikitable" style="text-align: center"|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-! Новое состояние центральной клетки| 0 || 1|| 0|| 1||1|| 0|| 1|| 0|}== Правило 110 =={{Определение|definition='''Правило 110''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.}}Правила перехода для Правила 110:{| class="wikitable" style="text-align: center"|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-! Новое состояние центральной клетки| 0 || 1|| 1|| 0||1|| 1|| 1|| 0|}Так как <tex>01101110 _2 = 110_10</tex>, данное правило называется Правилом 110. == Правило 184 =={{Определение|definitionWireworld ='''Правило 184''' {{---}} [[Линейный клеточный автомат, эквивалентность МТ|ЛКА]] с двумя состояниями (0 и 1).<br>}}Правила перехода для Правила 184:{| class="wikitable" style="text-align:center;"|-! Текущее состояние трёх соседних клеток| 111 || 110 || 101 || 100 || 011 || 010 || 001 || 000|-! Новое состояние центральной клетки| 1 || 0|| 1|| 1||1|| 0|| 0|| 0|} = Wireworld =
{{Определение
|definition=
Клеточный автомат '''Wireworld'''<ref>Трофимов Д., Наумов Л. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007. URL: http://is.ifmo.ru/works/wireworld/</ref> представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний.
}}
=== Состояния ===
[[Файл:Wireworld_states_meaning_table.jpg|500px|700px|thumb|center|Состояния автомата Wireworld]]
=== Правила ===
На каждом шаге автомата ко всем клеткам применяются следующие правила:
# Пустая клетка остается пустой.
# Клетка, находящаяся в состоянии «голова электрона» переходит в состояние «хвост электрона».
# Клетка, находящаяся в состоянии «хвост электрона» переходит в состояние «проводник».
# Клетка, находящаяся в состоянии «проводник» переходит в состояние «голова электрона», в том случае, если среди соседних клеток ровно одна или две находятся в состоянии «голова электрона». Во всех остальных случаях «проводник» остается «проводником».<br>
При применении данных правил используется [[#moore_neighborhood | окрестность Мура]] – считается, что с данной
клеткой соседствуют все восемь ее непосредственных соседей.
=== Общие закономерности ===
Электрон передвигается со скоростью одна клетка за шаг. Если по проводу навстречу идут два электрона, при столкновении они исчезают. При достижении электроном разветвления проводов по каждому из направлений, кроме исходного, уходит по электрону. Если к разветвлению одновременно подходит <tex>2</tex> и более электронов, все они исчезают. При толщине провода в <tex>2</tex> клетки поведение электронов аналогично обычному, при большей толщине поведение становится хаотичным.
=== Основные элементы ===
Большие коллекции функциональных элементов имеются в пакетах 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>
[[Файл:Tact_generator_wireworld.jpg|100px|300px|thumb|center|Тактовый генератор]]
==== Диод ====
Этот функциональный элемент имеет две точки подсоединения к проводам – вход и выход, и его действие состоит в том, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезают. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направлении.
<br>
[[Файл:Diode_wireworld.jpg|100px|300px|thumb|center|Диод]]
==== Логические элементы OR, XOR и NAND ====
Каждый из этих элементов имеет по 2 входа и выход. Наличие электрона на входе соответствует логическому значению «единица», отсутствие – логическому значению «ноль». Электрон на выходе появляется согласно таблице истинности соответствующей логической операции.<br>
* Так, для элемента '''OR''' электрон на любом из входов, или электроны на обоих входах одновременно дают электрон на выходе.<br>
[[File:NAND_wireworld.jpg|75px|150px|center|thumb|NAND]]
==== Двоичный сумматор ====
Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор. Его функция заключается в том, что при подаче на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. На
рисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.
