Wireworld

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
2 діоди, верхній напрямлений за струмом, нижній — проти

Wireworldклітинний автомат, запропонований Браяном Сільверманом[en] у 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. Процитовано 4 лютого 2016.
  3. Mark Owen. The Wireworld Computer. Архів оригіналу за 13 лютого 2013. Процитовано 4 лютого 2016.

Посилання

[ред. | ред. код]