110. szabály

A 110-es szabály ( angolul  Rule 110 ) az elemi celluláris automata egyik változata , amelyben a transzformációs eredmények sorozata egy 01101110 bináris sorozatot alkot, amely a 110-es decimális szám bináris reprezentációja. Minden elemi sejtautomata egy végtelen szalag szekvenciálisan elhelyezett cellákból, amelyeknek csak két állapota lehet (0 és 1), ugyanakkor a cella jövőbeli állapota három cella aktuális értékétől függ - saját maga és két legközelebbi szomszédja.

A 110-es szabály szerint működő automatát a káosz és a stabilitás határán való viselkedés jellemzi . Ugyanez a viselkedés velejárója az " Élet " játéknak. A 110-es szabállyal rendelkező cellás automata bizonyítottan Turing-komplett , vagyis bármilyen számítási eljárás megvalósítható vele. Talán ez a legegyszerűbb Turing-komplett rendszer [1] .

Definíció

A legegyszerűbb cellás automatákban egy nullákból és egyesekből álló egydimenziós tömb egy szabályrendszer szerint alakul. A cella értéke a következő lépésben ennek a cellának és két szomszédjának (bal és jobb) aktuális állapota alapján alakul ki. A 110. szabály a következő átalakításokat tartalmazza:

A 110-es szabály elnevezést a Wolfram-kód határozza meg  – a 01101110 bináris sorozat decimálisra konvertálva a 110-es számot adja.

A logikai algebra szimbólumokban a szabály felírható [2] :

Matematikai átalakítási lehetőség:

Történelem

Stephen Wolfram megvizsgálta a három szomszédos szalagcellából álló legegyszerűbb sejtautomaták összes lehetséges változatát, amelyek mindegyike csak két állapotot vehet fel (1/0, tele/üres, élő/halott). Összesen három szomszédos cellánál 8 opció lehet az aktuális állapothoz. Mivel mindegyik opció a központi cellának csak két új állapotát tudja generálni, a legegyszerűbb automaták száma összesen 256. Ha az aktuális állapot mind a 8 opciója esetén a végső állapotok halmaza decimális számként értelmeződik a bináris kódban , akkor ennek a decimális számnak az összehasonlítását kapjuk egy egyjegyű halmaztranszformációs utasítással az egyik legegyszerűbb cellás automatához. Wolfram „ Szabályoknak ” nevezte őket a megfelelő számmal.

Amikor kezdeti állapotként kaotikus sorozatot állított be, Wolfram a kapott transzformációs eredményeket különböző szabályok szerint 4 osztályba csoportosította:

1. Konvergáljon egy nulla vagy egy állapotba.
2. ciklikus vagy stabil állapotba konvergálnak.
3. Fenntartani a kaotikus, instabil állapotot.
4. Mindkét régió ciklikus vagy stabil állapotú, valamint olyan struktúrák alakulnak ki, amelyek komplex módon kölcsönhatásba lépnek egymással.

Az egyetemesség bizonyítéka

Wolfram a sejtautomaták tanulmányozásának eredményeit az A New Kind of Science (2002-ben megjelent) könyv formájában publikálta. A tanulmányozásban Matthew Cook segítette. A 4. osztályú gépkarabélyok jelentős érdeklődést váltottak ki Wolfram iránt. Köztük volt a 110-es szabály, amelyről Wolfram 1985-ben azt javasolta, hogy Turing-teljes [1] , vagyis lehetséges univerzális számításokat végezni. Matthew Cook bizonyítékot dolgozott ki Wolfram sejtésére, amelyet Cook a Santa Fe Institute konferenciáján mutatott be 1998-ban.

Mivel Cook munkája nagyrészt Wolfram kutatásán alapult, de csak az egyik megfontolt szabálynak szentelték, Wolfram nem akarta, hogy a bizonyítékot a saját könyve megjelenése előtt közzétegyék, amely az ilyen sejtautomaták teljes készletének figyelembevételével foglalkozik. . Ez perhez vezetett a könyven való munka során szerzett információkra vonatkozó titoktartási megállapodás megsértése miatt [3] . A konferencián elhangzott bizonyítás ugyan nem szerepelt a konferencia anyagának papíralapú változatában, ennek ellenére ismertté vált a létezése. 2004-ben Cook bizonyítékát publikálták a Wolfram "Complex Systems" című folyóiratában (15. szám, 1. kötet) [1] .

A 110. szabály egyetemességének bizonyítására Cook megmutatta, hogy lehetővé teszi egy másik számítási modell szimulálását - a ciklikus címkék rendszerét., ami univerzális.

Először három önreprodukáló sablonstruktúrát emelt ki. Az ábrákon az idő fentről lefelé halad: a felső sor a kezdeti állapotot, minden további sor pedig a következő iteráció állapotát. Az ábra bal szélső struktúrája két cellát jobbra tol el, és három generációnként ismétlődik, balról jobbra átlós útvonalat alkotva a háttérmintán.

Az ábra közepén ábrázolt szerkezet nyolc cellát tol el balra, és harminc generációnként ismétlődik, jobbról balra átlós szerkezetet alkotva ugyanazon a háttérmintán.

Az ábra jobb szélső szerkezete hét generációnként megismétli az előző állapotokat elmozdulások nélkül, és mozdulatlan marad az alapháttér előtt.

Cook ezután kidolgozott egy módot e struktúrák kombinációinak kölcsönhatására, így az eredmény számításként értelmezhető.

Jegyzetek

1. ↑ 1 2 3 Cook, Matthew (2004). „Universalitás az elemi celluláris automatákban” (PDF) . összetett rendszerek . 15 , 1-40. Archivált (PDF) az eredetiből ekkor: 2016-05-28 . Letöltve: 2021-02-10 . Elavult használt paraméter |deadlink=( súgó )
2. ↑ 110. szabály – Wolfram|Alfa . Letöltve: 2021. február 10. Az eredetiből archiválva : 2021. január 29. (határozatlan)
3. ↑ Giles, Jim (2002). – Miféle tudomány ez? természet . 417 (6886): 216-218. Bibcode : 2002Natur.417..216G . DOI : 10.1038/417216a . PMID  12015565 .