Sääntö 110

Sääntö 110 ( englanninkielinen  sääntö 110 ) on yksi alkeissoluautomaatin muunnelmista, jossa muunnostulosten sarja muodostaa binäärisekvenssin 01101110, joka on desimaaliluvun 110 binääriesitys. Kaikki solukkoautomaatit ovat ääretöntä nauhaa. peräkkäin sijoitetuista soluista, joilla voi olla vain kaksi tilaa (0 ja 1), ja samalla solun tuleva tila riippuu kolmen solun - itsensä ja sen kahden lähimmän naapurin - nykyisistä arvoista.

Säännön 110 mukaan toimivalle automaatille on ominaista käyttäytyminen kaaoksen ja vakauden rajalla . Sama käyttäytyminen on luontaista peliin " Elämä ". Solukkoautomaatti , jolla on sääntö 110, on todistettu Turing-täydelliseksi , eli sillä voidaan toteuttaa mikä tahansa laskennallinen proseduuri. Ehkä tämä on yksinkertaisin Turingin täydellinen järjestelmä [1] .

Määritelmä

Yksinkertaisimmissa solukkoautomaateissa yksiulotteinen nollien ja ykkösten joukko muunnetaan sääntöjen mukaan. Solun arvo seuraavassa vaiheessa muodostetaan tämän solun ja sen kahden naapurin (vasemman ja oikean) nykyisen tilan perusteella. Säännössä 110 on seuraavat muunnokset:

Nimi Sääntö 110 määräytyy Wolfram-koodin avulla  - binäärisekvenssi 01101110, kun se muunnetaan desimaaliluvuksi, antaa luvun 110.

Boolen algebrasymboleissa sääntö voidaan kirjoittaa [2] :

Matemaattinen muunnosvaihtoehto:

Historia

Stephen Wolfram tarkasteli kaikkia mahdollisia muunnelmia yksinkertaisimmista soluautomaateista, jotka koostuvat kolmesta vierekkäisestä nauhasolusta, joista jokainen voi ottaa vain kaksi tilaa (1/0, täysi/tyhjä, elossa/kuollut). Yhteensä kolmelle naapurisolulle voi olla 8 vaihtoehtoa nykyiselle tilalle. Koska kukin näistä valinnoista voi tuottaa vain kaksi uutta keskussolun tilaa, niin yksinkertaisimpien automaattien kokonaismäärä on 256. Jos nykyisen tilan kaikille 8 vaihtoehdolle lopputilojen joukko tulkitaan binäärikoodin desimaaliluvuksi , niin saamme tämän desimaaliluvun vertailun yksinumeroisten joukkomuunnosohjeiden kanssa yhdelle yksinkertaisimmista soluautomaateista. Wolfram kutsui niitä " säännöiksi " vastaavalla numerolla.

Asettaessaan kaoottisen sekvenssin alkutilaksi Wolfram ryhmitti tuloksena saadut muunnostulokset eri sääntöjen mukaan 4 luokkaan:

1. Konvergoi tilaan yksi nolla tai yksi.
2. konvergoi sykliseen tai vakaaseen tilaan.
3. Säilytä kaoottinen, epävakaa tila.
4. Muodostuvat molemmat alueet, joilla on syklinen tai stabiili tila, sekä rakenteita, jotka ovat vuorovaikutuksessa toistensa kanssa monimutkaisilla tavoilla.

Todiste universaalisuudesta

Wolfram valmisteli soluautomaattien tutkimuksen tulokset julkaistavaksi kirjan A New Kind of Science (julkaistu vuonna 2002) muodossa. Häntä avusti tutkimuksessa Matthew Cook. 4. luokan rynnäkkökiväärit herättivät huomattavaa kiinnostusta Wolframiin. Niiden joukossa oli sääntö 110, josta Wolfram ehdotti vuonna 1985, että se on Turing-täydellinen [1] , eli on mahdollista suorittaa universaaleja laskelmia. Matthew Cook kehitti todisteen Wolframin olettamuksesta, jonka Cook esitteli Santa Fe Instituten konferenssissa vuonna 1998.

Koska Cookin työ perustui suurelta osin Wolframin tutkimukseen, mutta oli omistettu vain yhdelle harkituista säännöistä, Wolfram ei halunnut, että todiste julkaistaan ​​ennen kuin hänen oma kirjansa, joka oli omistettu tällaisten soluautomaattien kokonaisuuden tarkasteluun, julkaistaan. . Tämä johti oikeudenkäyntiin salassapitosopimuksen rikkomisesta kirjan parissa työskennellessään saatujen tietojen osalta [3] . Vaikka konferenssissa esitetty todiste ei sisältynyt konferenssijulkaisun paperiversioon, sen olemassaolo tuli kuitenkin tiedoksi. Vuonna 2004 Cookin todistus julkaistiin Wolframin lehdessä "Complex Systems" (numero 15, osa 1) [1] .

Todistaakseen säännön 110 universaalisuuden Cook osoitti, että sen avulla voidaan simuloida toista laskennallista mallia - syklisten tunnisteiden järjestelmää., joka on universaali.

Ensin hän nosti esiin kolme itseään toistuvaa mallirakennetta. Kuvissa aika kulkee ylhäältä alas: ylärivi edustaa alkutilaa ja jokainen seuraava rivi edustaa tilaa seuraavassa iteraatiossa. Kuvan vasemmanpuoleisin rakenne siirtää kahta solua oikealle ja toistaa joka kolmas sukupolvi muodostaen diagonaalisen polun vasemmalta oikealle taustakuvion poikki.

Kuvan keskellä esitetty rakenne siirtää kahdeksan solua vasemmalle ja toistuu joka 30. sukupolvi muodostaen diagonaalisen rakenteen oikealta vasemmalle saman taustakuvion päälle.

Kuvan oikeanpuoleisin rakenne toistaa edelliset tilat ilman siirtymiä seitsemän sukupolven välein ja pysyy liikkumattomana pohjataustaa vasten.

Cook keksi sitten tavan, jolla näiden rakenteiden yhdistelmät voivat olla vuorovaikutuksessa niin, että tulos voidaan tulkita laskennaksi.

Muistiinpanot

1. ↑ 1 2 3 Cook, Matthew (2004). "Universaalisuus perussoluautomaatissa" (PDF) . monimutkaiset järjestelmät . 15 :1-40. Arkistoitu (PDF) alkuperäisestä 28.5.2016 . Haettu 2021-02-10 . Käytöstä poistettu parametri |deadlink=( ohje )
2. ↑ sääntö 110 - Wolfram|Alpha . Haettu 10. helmikuuta 2021. Arkistoitu alkuperäisestä 29. tammikuuta 2021. (määrätön)
3. ↑ Giles, Jim (2002). "Mitä tiedettä tämä on?" luonto . 417 (6886): 216-218. Bibcode : 2002Natur.417..216G . DOI : 10.1038/417216a . PMID  12015565 .