Вольфрамовіві елементарні клітинні автомати: 256 правил та край обчислень

Визначення та кодування

Елементарна клітинна автоматизація (ЕКА) — це одновимірна, двостаново, трисусідня клітинна автоматизація. Універс є бінарною стрічкою — кожен елемент містить 0 (білий) або 1 (чорний) — і на кожному дискретному кроці кожен елемент одночасно оновлюється на основі себе та його негайно лівого та правого сусідів. Оскільки кожне сусідство має 2³ = 8 можливих конфігурацій, і правило повинно вказувати один з 2 виходів для кожного, існує 2⁸ = 256 можливих правил. Правило 0 відображає кожне сусідство на 0 (всі клітини помирають); Правило 255 відображає кожне сусідство на 1 (всі клітини живуть назавжди); Правила 30 і 110 знаходяться на протилежних кінцях спектру складності.

Читання таблиці правил

Щоб розшифрувати правило N, запишіть N у двійковій системі з позначенням 8 біт. k-тий біт справа зправа вказує, який вихід генерує околиця з числовою вартістю k:

Правило 110 = 01101110₂ околиця: 111 110 101 100 011 010 001 000 вихід: 0 1 1 0 1 1 1 0 Стандартна візуалізація стоїть вниз за часом — рядок 0 є початковою умовою (окремий чорний елемент на білому є канонічним), рядок 1 після одного кроку, і так далі. З 256 правил багато еквівалентні під віддзеркаленням або кольоровим доповненням; після врахування обох симетрій існує лише 88 дійсно різних правил. Правила 30 та його дзеркало Правило 86 створюють різні візерунки, але однакову складність; Правило 110 та Правило 137 є дзеркальними один до одного.

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

Rule 110: доказ універсального обчислення

Matthew Cook доказав у 1994 році (опублікований у 2004 році після судового спору щодо прав на видання), що Правило 110 може моделювати циклічну систему тегів, переписування системи, відомої як Turing-повна. Просторові та часові діаграми Правила 110 містять постійні рухомі структури, звані частинками, вбудовані в періодичний фон квазіперіоду 14, який називається «ефіром». Ключовим внеском Cook’а було те, що зіткнення частинок — приблизно 16 різних типів взаємодії — достатньо багаті, щоб моделювати операції додавання та видалення системи тегів, а ефір діє як порожня стрічка, а частинки кодують символи даних. Оскільки будь-яка машина Тюрінга зводиться до неї, питання «Чи Правило 110, починаючи з умови X, коли-небудь виробляє 1?» є невизначеним, еквівалентним проблемі зупинки — вражаючий результат для правила лише з 8 бінарними ступенями свободи.

Rule 184 і рух транспорту

Не кожна значуща умова моделює хаос чи обчислення. Умова 184 – це мінімальна модель руху одного автомобільного потоку в односторонній смузі: клітини представляють ділянки дороги, стан 1 означає наявність автомобіля, і автомобіль рухається праворуч, якщо наступна клітина порожня, інакше він залишається на місці. Умова правильно відтворює фазу безперешкодного руху при щільності нижче 0,5, утворення заторів при щільності вище її, поширення ударних хвиль назад через затор та збереження кількості автомобілів – найпростіший клітинний автомат, який демонструє обидва етапи моделі Nagel-Schreckenberg Fuller.

Змінні правила та більші околиці

Правило CA є зворотним, якщо кожен стан має рівно одного попередника. Серед 256 елементарних правил лише правило 51 (доповнення) і правило 204 (ідентичність) є зворотними — Тофлі та Марголус розробили формалізм блоку CA спеціально для побудови зворотних 2D правил для моделювання часової невідворотності фізики. Вольфраму також вдалося поширити вивчення на правила з k кольорів, радіус-r: для k=2, радіус=2 (п’ятиклетова околиця) існує приблизно 4 мільярди правил, 2³² , де код Вольфрама узагальнює той самий спосіб — правило N відображає конфігурацію околиці i в біт i з N.

Frequently asked questions

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

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