Wireworld

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
2 диода, верхний направлен по току, нижний — против

Wireworldклеточный автомат, предложенный Брайаном Сильверманом (англ.) в 1987 году, смоделированный в его программе Phantom Fish Tank. Автомат стал более известен после опубликования статьи в колонке «Computer Recreations» журнала Scientific American[1]. Wireworld в особенности пригоден для симуляции электронных логических элементов, или «гейтов». Несмотря на простоту правил, Wireworld является полным по Тьюрингу.

Правила[править | править вики-текст]

2 генератора тактовых импульсов посылают электроны в вентиль XOR

Клетка в Wireworld может находиться в одном из четырех состояний:

  1. Пустая
  2. Голова электрона
  3. Хвост электрона
  4. Проводник

В программном обеспечении они нумеруются от 0 до 3 значительно чаще, чем от 1 до 4. В примере, данном здесь, стадии обозначены соответственно цветами: черным, синим, красным, желтым.

Как и во всех клеточных автоматах, время разделено на шаги, называемыми поколениями (иногда «гены» или «тики»). Клетки ведут себя следующим образом:

  • Пустой → Пустой
  • Голова электрона → Хвост электрона
  • Хвост электрона → Проводник
  • Проводник → Голова электрона при условии, что на соседних клетках есть ровно 1 или 2 головы электронов, иначе остаются проводниками.

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

Применения[править | править вики-текст]

Среди объектов, созданных во вселенной Wireworld — муравей Лэнгтона (в Wireworld возможно создать любой образец муравья Лэнгтона)[2] и компьютер Wireworld, полный по Тьюрингу компьютер, осуществленный с помощью клеточного автомата[3].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Computer recreations: The cellular automata programs that create Wireworld, Rugworld and other diversions, Scientific American (1990) by A K Dewdney
  2. Nyles Heise. Wireworld. Архивировано из первоисточника 13 февраля 2013.
  3. Mark Owen. The Wireworld Computer. Архивировано из первоисточника 13 февраля 2013.

Ссылки[править | править вики-текст]