Regel 110

Regel 110 ( engelsk  Rule 110 ) er en af ​​varianterne af den elementære cellulære automat , hvor sekvensen af ​​transformationsresultater danner en binær sekvens 01101110, som er den binære repræsentation af decimaltallet 110. Alle elementære cellulære automater er et uendeligt bånd af sekventielt placerede celler, der kun kan have to tilstande (0 og 1), og samtidig afhænger cellens fremtidige tilstand af de aktuelle værdier af tre celler - sig selv og dens to nærmeste naboer.

En automat, der fungerer efter regel 110, er karakteriseret ved adfærd på grænsen af ​​kaos og stabilitet . Den samme adfærd er iboende i spillet " Livet ". En cellulær automat med regel 110 har vist sig at være Turing-komplet , det vil sige, at enhver beregningsprocedure kan implementeres ved hjælp af den. Måske er dette det enkleste Turing-komplette system [1] .

Definition

I de enkleste cellulære automater transformeres et endimensionelt array af nuller og enere i henhold til et sæt regler. Værdien af ​​cellen i det næste trin dannes baseret på den aktuelle tilstand af denne celle og dens to naboer (venstre og højre). Regel 110 har følgende sæt af transformationer:

Navnet Regel 110 bestemmes af Wolfram-koden  - den binære sekvens 01101110, når den konverteres til decimal vil give tallet 110.

I booleske algebrasymboler kan reglen skrives [2] :

Mulighed for matematisk konvertering:

Historie

Stephen Wolfram overvejede alle mulige varianter af den enkleste cellulære automat, bestående af tre nabobåndceller, som hver kun kan tage to tilstande (1/0, fuld/tom, levende/død). I alt kan der være 8 muligheder for den nuværende tilstand for tre naboceller. Da hver af disse muligheder kun kan generere to nye tilstande i den centrale celle, så er det samlede antal af de simpleste automater 256. Hvis for alle 8 muligheder i den aktuelle tilstand fortolkes sættet af endelige tilstande som et decimaltal i binær kode , så vil vi få en sammenligning af dette decimaltal med en enkeltcifret sæt transformationsinstruktioner for en af ​​de enkleste cellulære automater. Wolfram kaldte dem " Regler " med det tilsvarende nummer.

Da Wolfram indstillede en kaotisk sekvens som starttilstand, grupperede Wolfram de resulterende transformationsresultater i 4 klasser efter forskellige regler:

1. Konverger til en tilstand på et nul eller et.
2. konvergere til en cyklisk eller stabil tilstand.
3. Oprethold en kaotisk, ustabil tilstand.
4. Der dannes både regioner med cykliske eller stabile tilstande, såvel som strukturer, der interagerer med hinanden på komplekse måder.

Bevis for universalitet

Wolfram forberedte resultaterne af undersøgelsen af ​​cellulære automater til offentliggørelse i form af bogen A New Kind of Science (udgivet i 2002). Han blev assisteret i undersøgelsen af ​​Matthew Cook. 4. klasses stormgeværer vakte betydelig interesse hos Wolfram. Blandt dem var Regel 110, som Wolfram foreslog i 1985, at den er Turing-komplet [1] , det vil sige, at det er muligt at udføre universelle beregninger. Matthew Cook udviklede et bevis på Wolframs formodning, som Cook præsenterede på Santa Fe Institute -konferencen i 1998.

Da Cooks arbejde i vid udstrækning var baseret på Wolframs forskning, men kun var viet til én af de overvejede regler, ønskede Wolfram ikke, at beviset blev offentliggjort før udgivelsen af ​​hans egen bog, der var viet til overvejelse af hele sættet af sådanne cellulære automater . Dette førte til en retssag om overtrædelse af en tavshedspligt for oplysninger indhentet under arbejdet med bogen [3] . Selvom beviset, der blev præsenteret på konferencen, ikke var inkluderet i papirversionen af ​​konferencehandlingerne, blev dets eksistens ikke desto mindre kendt. I 2004 blev Cooks bevis offentliggjort i Wolframs tidsskrift "Complex Systems" (udgave 15, bind 1) [1] .

For at bevise universaliteten af ​​regel 110 viste Cook, at den tillader en at simulere en anden beregningsmodel - systemet med cykliske tags, som er universel.

Først udpegede han tre selvreproducerende skabelonstrukturer. I figurerne går tiden fra top til bund: den øverste linje repræsenterer starttilstanden, og hver efterfølgende linje repræsenterer tilstanden ved næste iteration. Strukturen længst til venstre i figuren flytter to celler til højre og gentages hver tredje generation og danner en diagonal bane fra venstre mod højre på tværs af baggrundsmønsteret.

Strukturen afbildet i midten af ​​figuren flytter otte celler til venstre og gentages hver tredive generation og danner en diagonal struktur fra højre mod venstre over det samme baggrundsmønster.

Strukturen længst til højre i figuren gentager de foregående tilstande uden forskydninger hver syvende generation og forbliver ubevægelig mod basisbaggrunden.

Cook udtænkte derefter en måde, hvorpå kombinationer af disse strukturer kunne interagere, så resultatet kunne fortolkes som en beregning.

Noter

1. ↑ 1 2 3 Cook, Matthew (2004). "Universalitet i elementære cellulære automater" (PDF) . komplekse systemer . 15 :1-40. Arkiveret (PDF) fra originalen 2016-05-28 . Hentet 2021-02-10 . Forældet parameter brugt |deadlink=( hjælp )
2. ↑ regel 110 - Wolfram|Alpha . Hentet 10. februar 2021. Arkiveret fra originalen 29. januar 2021. (ubestemt)
3. ↑ Giles, Jim (2002). "Hvad er det for en videnskab?". natur . 417 (6886): 216-218. Bibcode : 2002Natur.417..216G . DOI : 10.1038/417216a . PMID  12015565 .