Pravidlo 30 - Rule 30 - Wikipedia

Tento článek je o celulárním automatu. Pro rozhodnutí federálního soudu USA viz Federální pravidla občanského soudního řádu a depozice (zákon).
A Conus textil vzhled podobný pravidlu 30.[1]

Pravidlo 30 je základní buněčný automat představil Stephen Wolfram v roce 1983.[2] Použitím Wolframovo klasifikační schéma, Pravidlo 30 je pravidlo třídy III, zobrazující neperiodické, chaotický chování.

Toto pravidlo je obzvláště zajímavé, protože z jednoduchých, dobře definovaných pravidel vytváří složité, zdánlivě náhodné vzory. Z tohoto důvodu se Wolfram domnívá, že pravidlo 30 a celulární automaty obecně jsou klíčem k pochopení toho, jak jednoduchá pravidla vytvářejí složité struktury a chování v přírodě. Například vzor připomínající pravidlo 30 se objeví na skořápce široce rozšířeného druhu šneka Conus textil. Pravidlo 30 bylo také použito jako generátor náhodných čísel v Mathematica,[3] a byl také navržen jako možný proudová šifra pro použití v kryptografie.[4][5]

Pravidlo 30 je tak pojmenováno, protože 30 je nejmenší Wolframův kód který popisuje jeho sadu pravidel (jak je popsáno níže). Zrcadlový obraz, doplněk a zrcadlový doplněk pravidla 30 mají kódy Wolfram 86, 135 a 149.

Sada pravidel

Ve všech Wolframových elementárních celulárních automatech se uvažuje o nekonečném jednorozměrném poli buněk celulárního automatu s pouze dvěma stavy, přičemž každá buňka je v nějakém počátečním stavu. V diskrétních časových intervalech každá buňka spontánně mění stav na základě svého aktuálního stavu a stavu svých dvou sousedů. Pro pravidlo 30 je sada pravidel, která řídí další stav automatu:

aktuální vzor111110101100011010001000
nový stav pro středovou buňku00011110

Odpovídající vzorec je [left_cell XOR (central_cell OR right_cell)]. Říká se mu pravidlo 30, protože v binární, 000111102 = 30.

Následující diagram ukazuje vytvořený vzor s buňkami zabarvenými na základě předchozího stavu jejich sousedství. Tmavší barvy představují „1“ a světlejší barvy „0“. Čas se zvyšuje po svislé ose.

Celulární automaty se systémem Wolfram-rule-30.svg

Struktura a vlastnosti

Následující vzorec vychází z počátečního stavu, ve kterém je jedna buňka se stavem 1 (zobrazená jako černá) obklopena buňkami se stavem 0 (bílá).

Rule30-256-rows.png
Buněčný automat podle pravidla 30

Zde vertikální osa představuje čas a jakýkoli horizontální průřez obrazu představuje stav všech buněk v poli v určitém bodě ve vývoji vzoru. V této struktuře je přítomno několik motivů, například častý výskyt bílých trojúhelníků a dobře definovaný pruhovaný vzor na levé straně; struktura jako celek však nemá žádný patrný vzor. Počet černých buněk v generaci je dáno posloupností

1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... (sekvence A070952 v OEIS )

a je přibližně .

Chaos

Wolfram založil svou klasifikaci pravidla 30 jako chaotickou založenou především na jeho vizuálním vzhledu,[Citace je zapotřebí ] a později se ukázalo, že splňuje přísnější definice chaosu navržené Devaney a Knudson. Zejména podle kritérií Devaney se zobrazí pravidlo 30 citlivá závislost na počátečních podmínkách (dvě počáteční konfigurace, které se liší jen v malém počtu buněk, se rychle rozcházejí), její periodické konfigurace jsou husté v prostoru všech konfigurací, podle Cantorova topologie v prostoru konfigurací (existuje periodická konfigurace s jakýmkoli konečným vzorem buněk) a je míchání (pro libovolné dva konečné vzory buněk existuje konfigurace obsahující jeden vzor, ​​který nakonec vede ke konfiguraci obsahující druhý vzor). Podle Knudsonových kritérií zobrazuje citlivou závislost a existuje hustá oběžná dráha (počáteční konfigurace, která nakonec zobrazuje jakýkoli konečný vzorec buněk). Obě tyto charakterizace chaotického chování pravidla vyplývají z jednodušší a snadno ověřitelné vlastnosti pravidla 30: je vlevo permutativní, což znamená, že pokud dvě konfigurace C a D se liší ve stavu jedné buňky v poloze i, pak se po jednom kroku budou nové konfigurace v buňce lišit i + 1.[6]

Aplikace

Generování náhodných čísel

Jak je patrné z výše uvedeného obrázku, pravidlo 30 generuje zdánlivou náhodnost navzdory nedostatku čehokoli, co by bylo možné rozumně považovat za náhodný vstup. Stephen Wolfram navrhl použít jeho středový sloup jako a generátor pseudonáhodných čísel (PRNG); projde mnoha standardními testy náhodnosti a Wolfram dříve použil toto pravidlo v produktu Mathematica pro vytváření náhodných celých čísel.[7]

Sipper a Tomassini prokázali, že jako generátor náhodných čísel vykazuje pravidlo 30 špatné chování na a chi kvadrát test při použití na všechny sloupce pravidel ve srovnání s jinými generátory celulárních automatů.[8] Autoři také vyjádřili své znepokojení nad tím, že „Relativně nízké výsledky získané pravidlem 30 CA mohou být způsobeny skutečností, že jsme uvažovali N náhodných sekvencí generovaných paralelně, namísto jediného uvažovaného Wolframem.“[9]

Dekorace

Detail opláštění železniční stanice Cambridge North

The Železniční stanice Cambridge North je vyzdoben architektonickými panely zobrazujícími vývoj pravidla 30 (nebo ekvivalentně pod černo-bílým obrácením, pravidlo 135).[10] Návrh popsal jeho architekt jako inspirovaný Conwayova hra o život, jiný buněčný automat studovaný cambridgeským matematikem John Horton Conway, ale ve skutečnosti není založen na životě.[11][12]

Viz také

Reference

  1. ^ Stephen Coombes (únor 2009). „Geometrie a pigmentace mušlí“ (PDF). www.maths.nottingham.ac.uk. University of Nottingham. Citováno 2013-04-10.
  2. ^ Wolfram, S. (1983). "Statistická mechanika celulárních automatů". Rev. Mod. Phys. 55 (3): 601–644. Bibcode:1983RvMP ... 55..601W. doi:10.1103 / RevModPhys.55,601.
  3. ^ „Generování náhodných čísel“. Dokumentace Wolfram Mathematica 8. Citováno 31. prosince 2011.
  4. ^ Wolfram, S. (1985). "Kryptografie s celulárními automaty". Proceedings of Advances in Cryptology - CRYPTO '85. Přednášky z informatiky 218, Springer-Verlag. p. 429. doi:10.1007 / 3-540-39799-X_32.
  5. ^ Meier, Willi; Staffelbach, Othmar (1991). Msgstr "Analýza pseudonáhodných sekvencí generovaných celulárními automaty". Pokroky v kryptologii: Proc. Workshop o teorii a aplikaci kryptografických technik, EUROCRYPT '91. Přednášky z informatiky 547, Springer-Verlag. p. 186. doi:10.1007/3-540-46416-6_17.
  6. ^ Cattaneo, Gianpiero; Finelli, Michele; Margara, Luciano (2000). "Zkoumání topologického chaosu elementární dynamikou celulárních automatů". Teoretická informatika. 244 (1–2): 219–241. doi:10.1016 / S0304-3975 (98) 00345-4. PAN  1774395.
  7. ^ Lex Fridman (02.03.2018), MIT AGI: Computational Universe (Stephen Wolfram), vyvoláno 2018-03-07
  8. ^ Sipper, Moshe; Tomassini, Marco (1996). Msgstr "Generování paralelních generátorů náhodných čísel celulárním programováním". International Journal of Modern Physics C. 7 (2): 181–190. Bibcode:1996 IJMPC ... 7..181S. doi:10.1142 / S012918319600017X.
  9. ^ Stránka 6 z Sipper, Moshe; Tomassini, Marco (1996). Msgstr "Generování paralelních generátorů náhodných čísel celulárním programováním". International Journal of Modern Physics C. 7 (2): 181–190. Bibcode:1996 IJMPC ... 7..181S. doi:10.1142 / S012918319600017X.
  10. ^ Wolfram, Stephen (1. června 2017), „Panebože, je to pokryto pravidlem 30s!“, Blog Stephena Wolframa
  11. ^ Lawson-Perfect, Christian (23. května 2017), „Správná odpověď ze špatného důvodu: mobilní automat na nové stanici Cambridge North“, Aperiodikum
  12. ^ Purtill, Corinne. „Pocta britskému vlakovému nádraží slavnému matematikovi dala všechno do pořádku, kromě jeho matematiky“. Křemen. Citováno 2017-06-12.

externí odkazy