Модели клеточных автоматов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Basic defintions, references, wireworld definition, states&rules)
(Wireworld elements)
Строка 35: Строка 35:
  
 
== Основные элементы ==
 
== Основные элементы ==
 +
=== Тактовый генератор ===
 +
Данный элемент представляет собой "петлю" из клеток проводника, к которой подсоединен провод – выход генератора, и изначально содержит один электрон. С периодом, равным длине петли, этот электрон достигает точки соединения петли с выходом, и дальше разветвляется на два электрона, один из которых идет по выходу, второй – дальше по петле. Таким образом, этот элемент можно использовать для получения в проводе бесконечного количества электронов, следующих один за другим на расстоянии, регулируемом длиной петли.<br>
 +
[[Файл:Tact_generator_wireworld.jpg|100px|300px|thumb|center|Тактовый генератор]]
  
 +
=== Диод ===
 +
Этот функциональный элемент имеет две точки подсоединения к проводам – вход и выход, и его действие состоит в том, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезают. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направлении.
 +
<br>
 +
[[Файл:Diode_wireworld.jpg|100px|300px|thumb|center|Диод]]
 +
 +
=== Логические элементы OR, XOR и NAND ===
 +
Каждый из этих элементов имеет по 2 входа и выход. Наличие электрона на входе соответствует логическому значению "единица", отсутствие – логическому значению "ноль". Электрон на выходе появляется согласно таблице истинности соответствующей логической операции.<br>
 +
* Так, для элемента '''OR''' электрон на любом из входов, или электроны на обоих входах одновременно дают электрон на выходе.<br>
 +
* Для элемента '''XOR''' электрон на любом из входов дает электрон на выходе, но при одновременной подаче электронов на оба входа они исчезают, и электрон на выходе не создается.<br>
 +
* Элемент '''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.jpg|75px|150px|center|thumb|NAND]]
 +
 +
=== Двоичный сумматор ===
 +
Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор. Его функция заключается в том, что при подаче на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. На
 +
рисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии "проводник" по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.
 +
 +
[[File:Binary_summator_wireworld.jpg|75px|150px|center|thumb|Двоичный сумматор]]
 +
<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 компьютера с определенным набором инструкций и регистров, и реализация алгоритма перечисления простых чисел для этого компьютера
  
 
= См.также =
 
= См.также =

Версия 14:33, 24 июня 2020

Базовые определения

Определение:
Окрестность Мура ячейки — совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.

Окрестность Мура порядка [math]r[/math] — множество клеток, расстояние Чебышёва[1] до которых от данной клетки не превышает [math]r[/math].

Окрестность Мура порядка [math]r[/math] в двумерном случае представляет собой квадрат со стороной [math]2r + 1[/math][2].


Игра "Жизнь"

Коды Вольфрама

Wireworld

Определение:
Клеточный автомат Wireworld[3] представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний.


Состояния

Состояния автомата Wireworld

Правила

На каждом шаге автомата ко всем клеткам применяются следующие правила:

  1. Пустая клетка остается пустой.
  2. Клетка, находящаяся в состоянии "голова электрона" переходит в состояние "хвост электрона".
  3. Клетка, находящаяся в состоянии "хвост электрона" переходит в состояние "проводник".
  4. Клетка, находящаяся в состоянии "проводник" переходит в состояние "голова электрона", в том случае, если среди соседних клеток ровно одна или две находятся в состоянии "голова электрона". Во всех остальных случаях "проводник" остается "проводником".


При применении данных правил используется окрестность Мура – считается, что с данной клеткой соседствуют все восемь ее непосредственных соседей.

Общие закономерности

Электрон передвигается со скоростью одна клетка за шаг. Если по проводу навстречу идут два электрона, при столкновении они исчезают. При достижении электроном разветвления проводов по каждому из направлений, кроме исходного, уходит по электрону. Если к разветвлению одновременно подходит [math]2[/math] и более электронов, все они исчезают. При толщине провода в [math]2[/math] клетки поведение электронов аналогично обычному, при большей толщине поведение становится хаотичным.

Основные элементы

Тактовый генератор

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

Тактовый генератор

Диод

Этот функциональный элемент имеет две точки подсоединения к проводам – вход и выход, и его действие состоит в том, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезают. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направлении.

Диод

Логические элементы OR, XOR и NAND

Каждый из этих элементов имеет по 2 входа и выход. Наличие электрона на входе соответствует логическому значению "единица", отсутствие – логическому значению "ноль". Электрон на выходе появляется согласно таблице истинности соответствующей логической операции.

  • Так, для элемента OR электрон на любом из входов, или электроны на обоих входах одновременно дают электрон на выходе.
  • Для элемента XOR электрон на любом из входов дает электрон на выходе, но при одновременной подаче электронов на оба входа они исчезают, и электрон на выходе не создается.
  • Элемент NAND работает как тактовый генератор, и посылает электроны на выход во всех случаях, за исключением случая, когда на оба входа одновременно подаются электроны.

TODO: FIX FORMATTING

OR
XOR
NAND

Двоичный сумматор

Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор. Его функция заключается в том, что при подаче на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. На рисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии "проводник" по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.

Двоичный сумматор


Большие коллекции функциональных элементов имеются в пакетах Mirek's Cellebration[4] и Zillions of Games[5], а также на сайте WireWorld[6]. Кроме того, на сайте The Wireworld computer[7] приводится пример построения в WireWorld компьютера с определенным набором инструкций и регистров, и реализация алгоритма перечисления простых чисел для этого компьютера

См.также

Литература

  1. ↑ Расстояние Чебышёва URL: https://ru.wikipedia.org/wiki/Расстояние_Чебышёва
  2. ↑ Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html
  3. ↑ Трофимов Д., Наумов Л. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007. URL: http://is.ifmo.ru/works/wireworld/
  4. ↑ "Mirek's Cellebration". URL:http://mirekw.com/ca/index.html
  5. ↑ "Zillions of Games". URL:http://zillionsofgames.com
  6. ↑ "WireWorld". URL:http://karl.kiwi.gen.nz/CA-Wireworld.html.
  7. ↑ "The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Модели_клеточных_автоматов&oldid=74634»