Вовчий клеточний автомат: Правила, класи складності та гра……

Прості клітинні автомати — 256 правил

Простий клітинний автомат (ПКА) складається з одновимірної рядок бінарних комірок. На кожному кроці часу кожна комірка оновлюється одночасно, використовуючи однакову правило для комірки та її двох сусідів. Оскільки існує 2³ = 8 можливих конфігурацій сусідства та 2 можливі виходи на кожну з них, є рівно 2⁸ = 256 різних правил. Ця схема нумерації "Wolfram code" (1983 року) присвоює кожному правилу унікальне ціле число від 0 до 255; правила малюються шляхом еволюції з одноклітинного насіння, де час тече вниз, створюючи «просторовий-часовий діаграма» автомата.

Rule 30: 30 = 00011110₂
neighbourhood: 111 110 101 100 011 010 001 000
output:          0   0   0   1   1   1   1   0

Чотири класи складності Вольфрама

Вольфрам класифікував усі 256 елементарних правил у чотири якісні класи на основі довготривалого поведінки. Клас I — Однорідність: всі клітини колапсують до єдиного фіксованого стану незалежно від початкової умови (Правила 0, 8, 32). Клас II — Періодичність/Стабільність: клітини встановлюють прості періодичні або стабільні патерни (Правила 4, 19, 50). Клас III — Хаотичність: неперіодичні, здавалося б випадкові патерни, чутливі до початкових умов (Правило 30, 45, 73). Клас IV — Складність: довготривалі, неперіодичні, локалізовані структури, які взаємодіють складними способами, пов’язані з обчисленням та універсальністю (Правила 54, 106, 110). Поведінка Класу IV, на межі між порядком і хаосом, є «межою хаосу», в якій, за гіпотезою, також функціонують життя та когніція.

жива демонстрація · пов'язана симуляція● LIVE

Важливі правила: 30, 90, 110

Правило 30 створює хаотичний, нерегулярний малюнок з однієї живої клітини; його центральна колонка статистично випадкова, тому Вольфрам використовував її як вбудований псевдовипадковий генератор у Mathematica.

Правило 90 (XOR двох сусідніх лівих і правих стовпців, без урахування центрального) генерує трикутник Sierpiński — рядок n дорівнює Pascal'євому трикутнику за модулем 2.

Було доведено Мартіном Куком у 2004 році, що правило 110 є Turing-повним: правило, описане одним байтом, може симулювати будь-яку Turing машину, роблячи його найпростішою відомою універсальною обчислювальною системою.

Дві виміри: Гра Життя Конвея

У 2D CA клітини розташовані на сітці з використанням сусідства Ван Нею (4 ортогональних сусіди, що використовуються в реактивно-дифузійних системах) або сусідства Мора (всі 8 навколишніх клітин). Гра Життя, яку представив Джон Конвей у 1970 році, є двовимірною бінарною тоталістичною CA з сусідством Мора, що відповідає правилам B3/S23: мертва клітина народжується, коли навколо неї рівно 3 живі клітини, а жива клітина виживає, якщо навколо неї 2 або 3 живі клітини. З цих трьох правил виникає надзвичайна різноманітність — статичні зображення, такі як блок, колискові, як блискавка та пульсар, космічні кораблі, як слайдер, і гармати-слайдери, які безперервно емітують космічні кораблі. Гармата-слайдер плюс логічні ворота достатньо для моделювання будь-якого обчислення, роблячи Життя само по собі Turing-повним.

Застосування в науці та мистецтві

Алан Тюрінг, у своїй моделі реактивно-дифузії 1952 року, створює візерунки на хутрох тварин – від малюнків леопарда до смуг зебри – за допомогою механізму, подібного до CA, що передбачає дифузію та реакцію хімічних речовин-активаторів і інгібіторів. Модель Nagel-Schreckenberg є 1D CA, яка відтворює затори на дорогах без централізованого контролю, виникаючи повністю з локальних правил прискорення, гальмування та випадкового сповільнення. Художники та розробники ігор використовують CA для створення органічних текстур – правило 30 для генерації випадковості, гладкість birth-3/survival-2-3 для генерації печер та підземель, а також дифузійно-обмежене агрегування для росту кристалів.

Frequently asked questions

Скільки елементарних правил клітинної автоматики існує?

Існує рівно 256. Елементарна автоматика має бітове стан і сусідство з трьома клітинами (ліворуч, в центрі, праворуч), що дає 2³ = 8 можливих конфігурацій сусідства, кожна з яких повинна відображатися на один із 2 можливих виходів — отже, існує 2⁸ = 256 різних правил, нумеруваних від 0 до 255 за бінарною кодуванням Вольфрама, розробленим у 1983 році.

Які чотири класи складності визначає Вольфрам?

Класи I правил зводять будь-яке початкове положення до єдиного фіксованого однорідного стану. Правила Класу II застигають у простих періодичних або стабільних патернах. Правила Класу III створюють нерегулярні, хаотично виглядаючі візерунки, чутливі до початкових умов. Правила Класу IV створюють довготривалі, неперіодичні, локалізовані структури, які взаємодіють складними способами і пов'язані з обчислювальною універсальністю — "межа хаосу" між порядком і випадковістю.

Чи є Conway’s Game of Life клітинною автоматикою?

Так — це 2D бінарна тоталістична клітинна автоматика з Moore сусідством (8 сусідніх клітин) відповідно до правила B3/S23: мертва клітина народжується з рівно 3 живих сусідів, а жива клітина виживає з 2 або 3 живих сусідів. З цих трьох правил виникає надзвичайна колекція об'єктів, включаючи статичні композиції, колискові, швидківлиди, літачі та система в цілому є Turing-повністю комплексною.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.

▶ Відкрити симуляцію the simulation

Вовчий клеточний автомат: Правила, складність та гра Життя Конвея