Regel 110

Regel 110 ( engelska  regel 110 ) är en av varianterna av den elementära cellulära automaten , där sekvensen av transformationsresultat bildar en binär sekvens 01101110, som är den binära representationen av decimaltalet 110. Alla elementära cellulära automater är ett oändligt band av sekventiellt placerade celler som bara kan ha två tillstånd (0 och 1) och samtidigt beror cellens framtida tillstånd på de aktuella värdena för tre celler - sig själv och dess två närmaste grannar.

En automat som arbetar enligt regel 110 kännetecknas av beteende på gränsen mellan kaos och stabilitet . Samma beteende är inneboende i spelet " Livet ". En cellulär automat med regel 110 har visat sig vara Turing-komplett , det vill säga vilken beräkningsprocedur som helst kan implementeras med den. Kanske är detta det enklaste Turing-kompletta systemet [1] .

Definition

I den enklaste cellulära automaten omvandlas en endimensionell array av nollor och ettor enligt en uppsättning regler. Värdet på cellen i nästa steg bildas baserat på det aktuella tillståndet för denna cell och dess två grannar (vänster och höger). Regel 110 har följande uppsättning transformationer:

Namnet Regel 110 bestäms av Wolfram-koden  - den binära sekvensen 01101110 när den konverteras till decimal ger talet 110.

I booleska algebrasymboler kan regeln skrivas [2] :

Matematisk konverteringsalternativ:

Historik

Stephen Wolfram övervägde alla möjliga varianter av den enklaste cellulära automaten, bestående av tre närliggande tejpceller, som var och en endast kan ta två tillstånd (1/0, full/tom, levande/död). Totalt kan det finnas 8 alternativ för det aktuella tillståndet för tre närliggande celler. Eftersom vart och ett av dessa alternativ endast kan generera två nya tillstånd i den centrala cellen, är det totala antalet av de enklaste automaterna 256. Om för alla 8 alternativen i det aktuella tillståndet tolkas uppsättningen av sluttillstånd som ett decimaltal i binär kod , då kommer vi att få en jämförelse av detta decimaltal med en ensiffrig uppsättning transformationsinstruktioner för en av de enklaste cellulära automaterna. Wolfram kallade dem " regler " med motsvarande nummer.

När Wolfram ställde in en kaotisk sekvens som initialtillstånd, grupperade Wolfram de resulterande transformationsresultaten enligt olika regler i 4 klasser:

1. Konvergera till ett tillstånd av ett noll eller ett.
2. konvergera till ett cykliskt eller stabilt tillstånd.
3. Upprätthålla ett kaotiskt, instabilt tillstånd.
4. Båda regionerna med cykliska eller stabila tillstånd bildas, såväl som strukturer som interagerar med varandra på komplexa sätt.

Bevis på universalitet

Wolfram förberedde resultaten av studien av cellulära automater för publicering i form av boken A New Kind of Science (publicerad 2002). Han fick hjälp i studien av Matthew Cook. 4:e klassens automatgevär väckte stort intresse för Wolfram. Bland dem var regel 110, om vilken Wolfram föreslog 1985 att den är Turing-komplett [1] , det vill säga det är möjligt att utföra universella beräkningar. Matthew Cook utvecklade ett bevis på Wolframs gissningar, som Cook presenterade vid Santa Fe Institute -konferensen 1998.

Eftersom Cooks arbete till stor del baserades på Wolframs forskning, men endast ägnades åt en av de övervägda reglerna, ville Wolfram inte att beviset skulle publiceras före utgivningen av hans egen bok, ägnad åt övervägandet av hela uppsättningen av sådana cellulära automater . Detta ledde till en stämningsansökan om brott mot ett sekretessavtal för information som erhållits under arbetet med boken [3] . Även om beviset som presenterades på konferensen inte ingick i pappersversionen av konferenshandlingarna, blev dess existens känd. 2004 publicerades Cooks bevis i Wolframs tidskrift "Complex Systems" (nummer 15, volym 1) [1] .

För att bevisa universaliteten av regel 110 visade Cook att den tillåter en att simulera en annan beräkningsmodell - systemet med cykliska taggar, vilket är universellt.

Först pekade han ut tre självreproducerande mallstrukturer. I figurerna går tiden från topp till botten: den översta raden representerar initialtillståndet och varje efterföljande rad representerar tillståndet vid nästa iteration. Strukturen längst till vänster i figuren flyttar två celler åt höger och upprepas var tredje generation och bildar en diagonal bana från vänster till höger över bakgrundsmönstret.

Strukturen som avbildas i mitten av figuren flyttar åtta celler åt vänster och upprepas var trettionde generation och bildar en diagonal struktur från höger till vänster över samma bakgrundsmönster.

Strukturen längst till höger i figuren upprepar de tidigare tillstånden utan förskjutningar var sjunde generation och förblir orörlig mot basbakgrunden.

Cook utarbetade sedan ett sätt för kombinationer av dessa strukturer att interagera så att resultatet kunde tolkas som en beräkning.

Anteckningar

1. ↑ 1 2 3 Cook, Matthew (2004). "Universalitet i elementära cellulära automater" (PDF) . komplexa system . 15 :1-40. Arkiverad (PDF) från originalet 2016-05-28 . Hämtad 2021-02-10 . Utfasad parameter används |deadlink=( hjälp )
2. ↑ regel 110 - Wolfram|Alpha . Hämtad 10 februari 2021. Arkiverad från originalet 29 januari 2021. (obestämd)
3. ↑ Giles, Jim (2002). "Vad är det här för vetenskap?". naturen . 417 (6886): 216-218. Bibcode : 2002Natur.417..216G . DOI : 10.1038/417216a . PMID  12015565 .