Pravidlo 110

Pravidlo 110 ( anglicky  Rule 110 ) je jednou z variant elementárního celulárního automatu , ve kterém sekvence výsledků transformace tvoří binární sekvenci 01101110, což je binární reprezentace desetinného čísla 110. Všechny elementární celulární automaty jsou nekonečnou páskou sekvenčně umístěných buněk, které mohou mít pouze dva stavy (0 a 1) a zároveň budoucí stav buňky závisí na aktuálních hodnotách tří buněk - samotné a jejích dvou nejbližších sousedů.

Automat fungující podle pravidla 110 se vyznačuje chováním na hranici chaosu a stability . Stejné chování je vlastní hře „ Život “. Bylo prokázáno , že celulární automat s pravidlem 110 je Turingův úplný , to znamená, že pomocí něj lze implementovat jakýkoli výpočetní postup. Možná je to nejjednodušší Turingův úplný systém [1] .

Definice

V nejjednodušších celulárních automatech se jednorozměrné pole nul a jedniček transformuje podle sady pravidel. Hodnota buňky v dalším kroku je tvořena na základě aktuálního stavu této buňky a jejích dvou sousedů (vlevo a vpravo). Pravidlo 110 má následující sadu transformací:

Název Pravidlo 110 je určen Wolframovým kódem  – binární posloupnost 01101110 při převodu na desítkovou čárku dá číslo 110.

V symbolech booleovské algebry lze pravidlo zapsat [2] :

Možnost matematického převodu:

Historie

Stephen Wolfram zvažoval všechny možné varianty nejjednodušších celulárních automatů, skládajících se ze tří sousedních páskových buněk, z nichž každá může nabývat pouze dvou stavů (1/0, plná/prázdná, živá/mrtvá). Celkem může být pro tři sousední buňky 8 možností aktuálního stavu. Protože každá z těchto možností může generovat pouze dva nové stavy centrální buňky, pak je celkový počet nejjednodušších automatů 256. Pokud je pro všech 8 možností aktuálního stavu množina konečných stavů interpretována jako desítkové číslo v binárním kódu , pak získáme srovnání tohoto desetinného čísla s jednociferným souborem transformačních instrukcí pro jeden z nejjednodušších celulárních automatů. Wolfram je nazval „ Pravidla “ s odpovídajícím číslem.

Při nastavení chaotické sekvence jako počátečního stavu seskupil Wolfram výsledné výsledky transformace podle různých pravidel do 4 tříd:

1. Konvergujte do stavu jedna nula nebo jedna.
2. konvergují do cyklického nebo stabilního stavu.
3. Udržujte chaotický, nestabilní stav.
4. Vznikají jak oblasti s cyklickými nebo stabilními stavy, tak i struktury, které na sebe vzájemně působí složitým způsobem.

Důkaz univerzálnosti

Wolfram připravil výsledky studia buněčných automatů k publikaci v podobě knihy A New Kind of Science (vydané v roce 2002). Při studiu mu pomáhal Matthew Cook. Útočné pušky 4. třídy vzbudily u Wolframa značný zájem. Mezi nimi bylo pravidlo 110, o kterém Wolfram v roce 1985 navrhl, že je Turingovo úplné [1] , to znamená, že je možné provádět univerzální výpočty. Matthew Cook vyvinul důkaz Wolframovy domněnky, kterou Cook představil na konferenci Santa Fe Institute v roce 1998.

Vzhledem k tomu, že Cookova práce byla z velké části založena na Wolframově výzkumu, ale byla věnována pouze jednomu z uvažovaných pravidel, Wolfram nechtěl, aby byl důkaz zveřejněn před vydáním jeho vlastní knihy, věnované úvahám o celé množině takových celulárních automatů. . To vedlo k soudnímu sporu kvůli porušení smlouvy o mlčenlivosti o informacích získaných při práci na knize [3] . Důkaz prezentovaný na konferenci sice nebyl zařazen do tištěné verze sborníku z konference, nicméně o jeho existenci se vědělo. V roce 2004 byl Cookův důkaz publikován ve Wolframově časopise "Complex Systems" (číslo 15, svazek 1) [1] .

Aby dokázal univerzálnost pravidla 110, Cook ukázal, že umožňuje simulovat jiný výpočetní model - systém cyklických značek, který je univerzální.

Nejprve vybral tři samoreprodukující se šablonové struktury. Na obrázcích jde čas shora dolů: horní řádek představuje počáteční stav a každý následující řádek představuje stav v další iteraci. Struktura nejvíce vlevo na obrázku posouvá dvě buňky doprava a opakuje se každé tři generace, čímž tvoří diagonální cestu zleva doprava přes vzorek pozadí.

Struktura znázorněná ve středu obrázku posouvá osm buněk doleva a opakuje se každých třicet generací a vytváří diagonální strukturu zprava doleva přes stejný vzor pozadí.

Struktura zcela vpravo na obrázku opakuje předchozí stavy bez posunů každých sedm generací a zůstává nehybná proti základnímu pozadí.

Cook pak vymyslel způsob, jak kombinace těchto struktur interagovat, aby výsledek mohl být interpretován jako výpočet.

Poznámky

1. ↑ 1 2 3 Cook, Matthew (2004). „Univerzalita v elementárních celulárních automatech“ (PDF) . komplexní systémy . 15 :1-40. Archivováno (PDF) z originálu dne 28.05.2016 . Získáno 2021-02-10 . Použitý zastaralý parametr |deadlink=( nápověda )
2. ↑ pravidlo 110 - Wolfram|Alpha . Získáno 10. února 2021. Archivováno z originálu dne 29. ledna 2021. (neurčitý)
3. ↑ Giles, Jim (2002). "Co je to za vědu?". příroda . 417 (6886): 216-218. Bibcode : 2002Natur.417..216G . DOI : 10.1038/417216a . PMID  12015565 .