Wireworld
Wireworld — клітинний автомат, який 1987 року запропонував Браян Сільверман, змодельований у його програмі Phantom Fish Tank. Став відомим після опублікування статті в колонці «Computer Recreations» журналу Scientific American[1]. Wireworld особливо придатний для симуляції електронних логічних елементів, або «гейтів». Попри простоту правил, Wireworld є повним за Тюрінгом.
Правила
Клітина у Wireworld може перебувати в одному з чотирьох станів:
- Порожня
- Голова електрона
- Хвіст електрона
- Провідник
У програмному забезпеченні їх нумерують від 0 до 3 (рідше — від 1 до 4). На наведених тут малюнках стани позначено, відповідно, кольорами: чорним, синім, червоним, жовтим.
Як і у всіх клітинних автоматах, час розділено на кроки, які називають поколіннями (іноді «генами» або «тіками»). Клітини поводяться так:
- Порожня → порожня
- Голова електрона → хвіст електрона
- Хвіст електрона → провідник
- Провідник → голова електрона за умови, що на сусідніх клітинках є рівно 1 або 2 голови електронів, інакше залишається провідником.
У Wireworld використовується окіл Мура, що означає, що в перелічених вище правилах сусідніми вважаються клітинки на відстані ходу шахового короля.
Застосування
Серед об'єктів, створених у всесвіті Wireworld — мураха Ленгтона (у Wireworld можливо створити будь-який зразок мурахи Ленгтона)[2] і комп'ютер Wireworld, повний за Тюрінгом комп'ютер, втілений за допомогою клітинного автомата[3].
Див. також
Примітки
- ↑ Computer recreations: The cellular automata programs that create Wireworld, Rugworld and other diversions, Scientific American (1990) by A K Dewdney
- ↑ Nyles Heise. Wireworld. Архів оригіналу за 13 лютого 2013. Процитовано 4 лютого 2016.
- ↑ Mark Owen. The Wireworld Computer. Архів оригіналу за 13 лютого 2013. Процитовано 4 лютого 2016.
Посилання
- Wireworld [Архівовано 28 лютого 2016 у Wayback Machine.] на Rosetta Code
- Комп'ютер Wireworld на Java [Архівовано 3 березня 2016 у Wayback Machine.]