Mūsdienās diskrētie modeļi informātikā un matemātikā tiek plaši izmantoti un rada pētniecisku interesi.
Viens no uzskatāmākajiem un vieglāk saprotamajiem modeļiem ir šūnu automāts (ŠA). ŠA ir
laukums n-dimensionālajā telpā, kas izmainās laika gaitā un kas sastāv no šūnām, katra no kurām
var eksistēt vienā no vairākiem stāvokļiem. Katrai šūnai ir definēta kaimiņu šūnu kopa (kaimiņniecība),
kas atkarībā no noteiktiem nosacījumiem (likumiem), var ietekmēt šūnas stāvokli nākamajā
ŠA aīstības stadijā (paaudzē, iterācijā). Pirmoreiz tāds modelis, kas izstrādāts ar mērķi izveidot pašreproducējošo
sistēmu, tika prezentēts Džona fon Neimana darbos [32, 16] XX gadsimta vidū. Vēlāk
S. Volframs savā darbā “A New Kind of Science” [28] aprakstīja elementāro (viendimensionālo) ŠA
uzvedību, kuriem, kā atklājās, ir vairākas tiešas saites ar dabisko sistēmu uzvedību.
Īpašu pētniecisko interesi izraisa binārie divdimensionālie ŠA (ŠA uz plaknes, kuros katra šūna
var atrasties vienā no diviem stāvokļiem — “dzīva” vai “mirusi”). Šādiem ŠA likumi galvenokārt tiek
definēti ar “dzīvo” vai “mirušo” šūnu skaitu starp tās kaimiņiem (šādus ŠA sauc par totalistiskajiem).
Šāda veida ŠA pārstāve ir t. s. spēle “Dzīve” (SD) [8], kurā šūnu uzvedībai ir vairākas tādas īpašības,
kā struktūru stabilizācija uz patvaļīgi aizpildīta laukuma (PAL), periodisku un kustošu struktūru
eksistence u. c. (skat. sadaļu 2.3.2). Toties ne mazāk interesanta ir divdimensionālo bināro ŠA
uzvedība uz laukuma, kas ir sastādīts no regulāriem sešstūriem (6-laukums). Izveidot tādu ŠA uz
6-laukuma, kura šūnas uzvestos līdzīgi kā SD, mums likās nozīmīgs un interesants matemātisks
uzdevums.
Darba mērķis izpētīt SD un ŠA uz 6-laukuma; atrast likumus, pie kuriem ŠA uzvedība uz 6-laukuma
atbilstu pēc savām īpašībām SD.
Darba uzdevumi
• modelēt un analizēt elementāro šūnu struktūru (EŠS) uzvedību SD un ŠA uz 6-laukuma;
• teorētiski formulēt iespējamos likumus 6-laukumam, pie kuriem ŠA izrādītu SD īpašības;
• analizēt un salīdzināt ŠA uz 6-laukuma modelēšanas rezultātus ar teorētiskā pētījuma rezultātiem;
• pēc salīdzināšanas rezultātiem izpētīt un apkopot datus par ŠA uz 6-laukuma aīstības dinamiku;
• sistematizēt ŠA uz 6-laukuma raksturīgas struktūras.
3
Darba metodika
• informācijas meklēšana par SD šūnu struktūru uzvedības īpašībām;
• aīstības dinamikas un raksturīgo struktūru pētījums, izmantojot modelēšanas un analīzes
programmu;
• teorētiskā likumu atlase ŠA uz 6-laukuma, balstoties uz šūnas stāvokļa izmaiņas varbūtību;
• datu par EŠS un patvaļīgi aizpildīta laukuma uzvedību sistematizācija un analīze, izmantojot
iegūtos modelēšanas rezultātā likumus;
• darba secinājumu formulēšana uz iegūto rezultātu pamata.
Darba struktūra Teorētiskajā daļā pārskatīta ŠA vēsture un rašanas cēloņi, to izmantošana un daži
no pastāvošajiem viendimensionāliem un divdimensionāliem ŠA. Sīkāk aprakstīta SD, šūnu uzvedības
īpašības tajā un raksturīgas struktūras. Aplūkota arī informācija par pastāvošajiem ŠA uz
6-laukuma.
Praktiskajā darba daļā aprakstīta eksperimenta gaita. Sīki aprakstīts EŠS uz 6-laukuma un SD
aīstības modelēšanas un analīzes programmas veidošanas process. Aprakstīta 4- un 6-laukuma
izteikšana datorformā, visu n-tās kārtas EŠS ģenerēšanas process uz šiem laukumiem, nākamas ŠA
paaudzes stāvokļa aprēķināšana, analītiskais aparāts laukuma struktūru stāvokļa novērtēšanai un
datu par EŠS aīstības iznākumu statistiskas apkopošanas metode. Izklāstīta matemātiskā SD līdzīgu
likumu aprēķināšana 6-laukumam. Aprakstīta arī visu iespējamo likumu ģenerēšana binārajiem
ŠA uz n-laukuma. Visatbilstošākie likumi salīdzināti ar matemātiski iegūtiem likumiem pēc to uzvedības
atbilstības SD. Pēc eksperimenta apraksta iegūtie rezultāti apkopoti un analizēti atbilstoši
darba mērķiem, formulēti secinājumi.
Darbam ir pielikumi: izmantoto terminu vārdnīca; izmantoto datorprogrammu kodu; tabula, kurā
ir sistematizētas raksturīgas atrastajiem likumiem struktūras un apkopoti galvenie darba rezultāti.
Zinātniski pētnieciskais darbs informātikā, 25 lapaspuses (neieskaitot pielikumus), 4 nodaļas,
33 literatūras avoti, 3 pielikumi, 25 aēli, 5 tabulas, 4 pirmkoda izdrukas, latviešu valodā.
4
Nodaļa 2
Teorētiskā daļa
ŠA vēsture aizsākās 1940. gadu sākumā Losalamosas Nacionālajā laboratorijā, kur Džons fon Neimans,
pamatojoties uz S. Ulama pētījumiem [24], ievieš ŠA jēdzienu. Fon Neimana piedāvātie mehānismi
tika izmantoti pašreproducējošo bioloģisko sistēmu pētījumos [32]. Praktiski vienlaikus ar
viņu šādām idejām pievērsās Konrads Cuzē, kurš cerēja tās pielietot mehānikas skaitliskajos modeļos
[30], un N. Vīners ar A. Rozenblutu ierosināmās vides modeļu veidošanā [25]. Tālākajos gados līdzīgas
idejas parādījās ar nelielām variācijām, toties, tādēļ, ka nebija vienotas terminoloģijas, darbos
bija liels atkārtojumu skaits. 1970. gados M. Gardners savā rakstā [8] popularizēja Džona Konveja
spēli “Dzīve”, un līdz ar to ŠA apstiprināja sevi ne tikai kā matemātisks diskrēts modelis, bet arī kā
aizraujoša t. s. spēle 0 spēlētājiem. 1983. gadā Stīvens Volframs publicē rakstu sēriju, kas bija veltīta
vieniem no vienkāršākajiem ŠA — t. s. elementārajiem (viendimensionālajiem binārajiem) ŠA [3],
dažiem no kuriem piemīt pilnība pēc Tjuringa (piemēram, likumam 110), un dažiem var atrast plašu
pielietojumu (piemēram, likumu 184 var izmantot transporta plūsmu modelēšanā) [28].
ŠA tiek izmantoti tādiem atšķirīgiem nolūkiem, kā gāzu uzvedības, uguns izplatīšanas ugunsgrēku
laikā, turbulences un bioloģiskas novecošanas modelēšanai, kristalizācijas procesu un elektriskās
strāvas izplatīšanās elektrotīklos pētīšanai [29]. Informātikā tie tiek izmantoti multimediju satura
ģenerēšanā [23], ciparu aēlu kompresijā [12], pat muzikālo kompozīciju veidošanā [22]. SD tiek
izmantota kibernētikā, bioloģijā un fizioloģijā, atsevišķās fizikas, ķīmijas un mehānikas nozarēs, arī
socioloģijā un filozofijā [33]. Tālāk mēs apskatīsim dažus no svarīgākajiem ŠA veidiem.
2.1 Fon Neimana ŠA
Džons fon Neimans bija pirmais, kas ieviesa ŠA jēdzienu, un tāpēc viņa pašreproducējošās mašīnas,
kas darbojas uz šūnu laukuma, koncepcija ir daudzu citu ŠA pamatā (piemēram, Nobili ŠA [18]). Fon
Neimana ŠA ir definēts uz bezgalīgā laukuma taisnstūra koordinātēs. Patvaļīgas šūnas kaimiņniecība
ir definēta kā to šūnu kopa, kurām ar doto šūnu ir kopējā mala (t. s. Fon Neimana kaimiņniecība
[17]). Katra šūna ir patstāvīgs ŠA, kas var atrasties vienā no 29 galīgiem stāvokļiem: bāzes stāvoklis,
8 tranzīta stāvokļi (jūtīgi pret informācijas nodošanu), 4 konfluentie stāvokļi (gatavi stāvokļa maiņai)
un 16 nodošanas stāvokļi (katrā no 4 virzieniem no katra no 4 nodošanai gataviem stāvokļiem).
Loģiskas prasības, kurus fon Neimans izvirzīja pašreproducējošajam ŠA, aprakstītas viņa lekcijā
“Vispārīgā un loģiskā automātu teorija” [16] un to būtība ir sekojoša. Ir nepieciešams, lai eksistētu
četri nosacīti bloki (A, B, C un D), katrs no kuriem izpilda kādas noteiktas funkcijas. Bloks A ir
elements, kas izpilda kādu operāciju atkarībā no saņemtās informācijas un saskaņā ar instrukcijām,
ko dod bloks D. Bloks B var veidot kopijas no šīm instrukcijām. Kontroles bloks C ir pieslēgts
blokiem A un B vienlaicīgi. C saņem instrukcijas, B veido no tām kopijas, bet A izpilda operāciju
5
(a)
(b)
Attēls 2.1. (a) Elementārā ŠA aīstība no vienas dzīvas šūnas 100 paaudzēs, pielietojot likumu 30;
(b) Likuma 30 shemātisks aēls.
atkarībā no tām. Ja A izpildītas operācijas rezultātā veidojas meitas automāts, tajā nodod instrukciju
kopiju no B (oriģināls paliek C). D, savukārt, satur visu informāciju, kas ir nepieciešama lai
izveidotu jaunu ABCD bloku sistēmu. Fon Neimans parādīja, ka šīs bāzes prasības ir nepieciešamas
pašreproducējošās sistēmas eksistencei. Fon Neimana ŠA ir šīs koncepcijas matemātiskā realizācija,
toties tā sarežģītība neļauj iegūt interesantus ŠA aīstības rezultātus, iepriekš neveicot aprēķinus
(pirmais pašreproducējošās mašīnas modelis tika realizēts tikai 1995. gadā [19]).
2.2 Elementārie ŠA
Elementārais ŠA ir pats vienkāršākais netriviālais viendimensionālais ŠA. Visi elementārie ŠA ir
binārie un var aīstīties saskaņā ar noteikto likumu komplektu, kas ir apzīmēts, izmantojot Volframa
kodu [27]. Kaimiņniecība dotajos ŠA sastāv no diviem šūnas tiešajiem kaimiņiem, tādēļ eksistē
23 = 8 elementāro šūnu struktūru (EŠS). Katra no tām noteiktā veidā nosaka centrālās šūnas stāvokli
nākamajā ŠA iterācijā (paaudzē), tādēļ pavisam eksistē 28 = 256 likumu komplektu. Pielietojot
dažus no tiem patvaļīgi aizpildītajiem laukumiem (PAL) vai noteiktajām laukuma sākuma konfigurācijām,
ŠA uzvedās interesanti, un, līdz ar to, ir vērts tuvāk ieskatīties šajos likumos.
Likums 30 (a. 2.1b) uzvedās haotiski, aīstoties no vienas dzīvās sākuma šūnas, veidojot sarežģītus
rakstus. Aēlā 2.1a ir parādīta ŠA aīstība pirmajās 100 iterācijās (paaudzes) no tāda sākuma
stāvokļa.
Līdzīgu uzvedību var novērot arī dabā (piemēram, Conus textile gliemju gliemežnīcu rakstos [20])
un, pēc Volframa domām, tā var kalpot par atslēgu izpratnei par to, ka sarežģīta sistēmu uzvedība var
pakļauties relatīvi vienkāršiem likumiem. Likumu 30 var arī lietot pseidogadījumskaitļu ģenerācijai
[26].
Likums 110 (a. 2.2) ir pirmais likums, kam tika pierādīta tā pilnība pēc Tjuringa [2] (iespēja realizēt
uz to izmantojošā ŠA jebkuru izskaitļojamu funkciju), izmantojot aīstības procesā atkārtojošās
struktūru uzvedības īpatnības.
6
Attēls 2.2. Likums 110 Attēls 2.3. Likums 184
Likums 184 (a. 2.3) aīstās triviāli no vienas dzīvās šūnas (nomirst pirmajā paaudzē), toties demonstrē
interesantu uzvedību pie gadījuma sākuma nosacījumiem: to pielietojošo ŠA var iedomāties
kā automašīnu kustību pa ceļu, kad viena satiksmes dalībnieka kustība ir atkarīga no cita, kas atrodas
viņam priekšā. Dažreiz likumu 184 dēvē par “ceļa likumu” [6].
2.3 Divdimensionālie binārie ŠA
2.3.1 Lengtona skudra
Attēls 2.4. Lengtona skudras ŠA aīstība
sākot no tukšā laukuma
(10 644 soļi)
Lengtona skudra ir ŠA veids, kas raksturojas ar vienkāršiem
likumiem, bet sarežģītu uzvedību aīstības gaitā. To
piedāvāja K. Lengtons 1986. gadā [13]. Šo ŠA var iedomāties
kā skudru uz bezgalīga taisnstūra laukuma, kura spēj
pārvietoties jebkurā no virzieniem fon Neimana apkārtnē
atbilstoši sekojošiem likumiem:
• atrodoties uz melnās šūnas, skudra pagriežas par 90°
pa labi un pārvietojas par vienu šūnu uz priekšu;
• atrodoties uz baltās šūnas, skudra pagriežas par 90°
pa kreisi un pārvietojas par vienu šūnu uz priekšu;
• atstājot šūnu, skudra nomaina tās krāsu.
Skudras kustība sākumā tukšajā laukumā pirmajos 104 soļos ir haotiskā, toties pēc tām tā sāk
būvēt bezgalīgu periodiski atkārtojošo struktūru (“šoseju”, a. 2.4).
Lengtona skudrai ir pierādīta pilnība pēc Tjuringa [7]. Papildus eksistē arī vispārinātais šī ŠA
variants, kurā šūnas var atrasties vairāk nekā divos stāvokļos, un to krāsas mainās cikliski. Šādi ŠA
demonstrē interesantu uzvedību, tajā skaitā arī veidojot simetriskās struktūras.
2.3.2 Spēle “Dzīve”
SD ir ŠA, kuru izveidoja britu matemātiķis Dž. Konvejs 1970. gadā [8]. SD, tāpat ka Lengtona skudra,
ir definēta uz bezgalīga taisnstūra laukuma (4-laukuma), kas sastāv no šūnām, kuras var atrasties
vienā no diviem stāvokļiem — “dzīva” vai “miruša”. Atšķirībā no Lengtona skudras, SD ir pieņemta
t. s. Mūra kaimiņniecība [14], ko definē kā to šūnu kopu, kurām ar doto šūnu ir vismaz viena kopējā
virsotne.
SD likumi ir vienkārši:
• ja šūna ir dzīva, tad nākamajā paaudzē tā paliek dzīva, ja tai ir 2 vai 3 dzīvi kaimiņi, pretējā
gadījuma tā nomirst;
7
• ja šūna ir miruša, tad nākamajā paaudzē tā atdzīvinās, tikai ja tai ir tieši 3 dzīvi kaimiņi.
Šādus likumus var apzīmēt vairākos veidos, piemēram,
1 : 2; 3 0 : 3; (2.1)
01100000j00100000: (2.2)
Mūsu darbā mēs pieturēsimies pie apzīmējumiem (2.2), par kuriem sīkāk ir pastāstīts sadaļā 3.3.
SD likumus Konvejs izvēlējās, izejot no dažām svarīgām īpašībām, kurām ir jāpiemīt ŠA:
• nedrīkst parādīties sprādziena aīstība (visām SD struktūrām eventuāli ir jāstabilizējas);
• no dažām nelielām struktūrām evolūcijas gaitā ir jāveidojas sarežģītākas struktūras ar nepārredzamu
uzvedību;
• ir jāeksistē iespējai uztaisīt pašreproducējošās struktūras (fon Neimana likumu izpilde [16]);
• likumiem ir jābūt pēc iespējas maksimāli vienkāršiem.
Struktūras, kas veidojas SD, var iedalīt sekojošās klasēs, katru no kurām mēs tālāk apskatīsim
sīkāk:
• oscilatori (periodiskās struktūras);
• stabilās struktūras (dažreiz tās ir ērti apskatīt kā oscilatorus ar periodu 1);
• bezgalīgi kustošās struktūras.
Sīkāk vairuma oscilējošo un stabilo struktūru parādīšanas biežums ir apskatīts rakstā [5], bet
mūsu darbā mēs to aprakstīsim pavirši.
Oscilatori
Struktūru stabilizācija SD bieži vien parādās kā dažu savā starpā nemijiedarbojošo oscilatoru izveide,
tāpēc šīs klases pārstāvji visbiežāk parādās uz laukuma, kad to aizpilda patvaļīgi [5], un ir vieni no
svarīgākajiem SD elementiem.
Pats izplatītākais SD oscilators ir blinker [5] — vienkāršākais oscilators ar periodu 2. Aēlā 2.5
ir parādīti tā divi stāvokļi.
Attēls 2.5. Blinker Attēls 2.6. Toad Attēls 2.7. Beacon
Nākamie oscilatori pēc parādīšanās biežuma ir aiecīgi Toad un Beacon, kuriem abiem arī ir
periodi 2 (aiecīgi a. 2.6 un 2.7). Ir jāatzīmē, ka to parādīšanas biežums jau ir par divām kārtām
mazāks, nekā Blinkeram, bet, novērojot PAL ar blīvumu 4–5 %, tos var redzēt relatīvi regulāri.
8
Attēls 2.8. Pulsar
Attēls 2.9. Pentadecathlon
Pie retākiem oscilatoriem pieder Pulsar ar periodu 3 (a. 2.8) un Pentadecathlon ar periodu 15.
Aēlā 2.9 ir aēlots viens no pēdējā periodiskiem stāvokļiem.
Bez šīm struktūrām var sastapties ar daudzumu citu oscilatoru, pat ar tādiem, kuru periods ir
lielāks par 300 vai šūnu ir vairāk par 5000. Ir vērts atzīmēt, ka, ja ar terminu “oscilators” domāt
visu lokāli oscilējošo struktūru kopumu, tad tā kopējais periods būs izsakāms kā mazākais kopējais
dalāmais no atsevišķu lokālu struktūru periodiem. Tādējādi var veidot oscilatorus ar vēl lielāku šūnu
skaitu un lielākiem periodiem.
Stabilās struktūras
Stabilajām struktūrām ir raksturīgs vidēji lielāks parādīšanas biežums nekā oscilatoriem. Visbiežāk
sastopamas stabilās struktūras uz PAL ir Block, Beehive, Loaf, Boat, Tub, Pond un Ship. Tās ir
parādītas aēlos 2.10a–g.
(a) (b) (c) (d) (e) (f) (g)
Attēls 2.10. SD stabilās struktūras: (a) Block, (b) Beehive, (c) Loaf, (d) Boat, (e) Tub, () Pond, (g) Ship
Svarīga daudzu stabilu struktūru īpašība ir iznīcināt planierus un citas tajās “ietriecošās” struktūras,
pašām nedeformējoties. Šī īpašība padara stabilās struktūras vērtīgas lielāku struktūru konstruēšanā.
Stabilās struktūras, tāpat ka oscilatori, var būt daudz un dažādu izmēru un var saturēt no
četrām līdz vairākiem tūkstošiem dzīvo šūnu.
Kustošās struktūras
Kustošās struktūras ir periodiskās struktūras, kas perioda laikā pārvietojas par noteiktu šūnu skaitu
noteiktā virzienā. Tām var definēt ātruma jēdzienu: ja struktūra ar periodu 1 pārvietojas par vienu
šūnu vienā laika solī, tad tās ātrums ir c. Patvaļīgai kustošai struktūrai ātrums izsakās kā
v =
cd
T
; (2.3)
kur d ir struktūras nobīde tās periodā T.
9
Attēls 2.11. Planiera aīstība laikā. Periodā T = 4 planieris pārvietojas par vienu šūnu gar Mūra
kaimiņniecības diagonāli.
(a) (b) (c)
Attēls 2.12. Kosmiskie kuģi: (a) viegls, (b) vidējs, (c) smags
Pie kustošām struktūrām pieder viena no pazīstamākajām SD struktūrām — planieris. Tā ātrums
ir c/4 un kustība notiek gar Mūra kaimiņniecības diagonālēm, kā ir parādīts aēlā 2.11.
Planieri ir svarīgi SD elementi, jo tie var sadurties savā starpā, veidojot jaunas struktūras (t. s.
planieru sintēze), tos ir viegli radīt (struktūra, kas ir pazīstama kā Gospera planieru lielgabals, spēj
periodiski ģenerēt planierus), tajā skaitā uz PAL [4]. Pie tā, planierus var pozicionēt tādā veidā, lai,
saduroties ar stabilām struktūrām, pēdējās mainītu savu pozīciju [11], kas ļauj uzkonstruēt loģiskos
elementus, un ar kuru palīdzību, savukārt, var pierādīt SD pilnību pēc Tjuringa. Šīs īpašības ir
raksturīgas arī citām kustošām struktūrām, bet darbs ar planieriem ir ērtāks to nelielu izmēra un
kustības ātruma dēļ.
Citi pazīstami kustošo struktūru pārstāvji ir viegls, vidējs un smags kosmiskie kuģi (aiecīgi
a. 2.12a–c).
2010. gadā tika paziņots par pašreproducējošās struktūras izveidi SD [15], kas pierādīja SD atbilstību
fon Neimana nosacījumiem. Šī struktūra ir kustošā un pārvietojas ar ātrumu 5120
33699586c gar
Ox asi un 1024
33699586c gar Oy asi.
2.4 ŠA uz sešstūru laukuma
ŠA uz sešstūra laukuma patlaban ir daudz mazāk izpētīti nekā uz taisnstūra laukuma. 6-Laukums
piesaista uzmanību, jo tā ir viena no tikai trim iespējām regulāri sadalīt bezgalīgu plakni [9] (citas
iespējas ir sadalīt ar kvadrātiem un vienādmalu trijstūriem). Pie tā 6-laukums ir dabā plaši izplatīts
sadalījums (bišu šūnas, bazalta stabi u. c.), kas ļauj to izmantot precīzākai dažu dabisko procesu
modelēšanai.
Eksistējošie binārie ŠA uz 6-laukuma ir aprakstīti darbā [21], kur ir piedāvāti likumi, kas nosaka
šūnas uzvedību ne tikai ar noteiktajos stāvokļos esošo kaimiņu skaitu, bet arī ar to savstarpējām
pozīcijām. Likumos in, Medium, ick, Golay un Preston (aiecīgi a. 2.13a–e, kur ir parādīti šūnas
stāvokļa maiņas nosacījumi) ir novērojamas kustošās struktūras un īpašie oscilatori (piemēram,
Spinner — oscilators, kurā struktūra sava perioda laikā apraksta riņķi ap tās centrālo šūnu). Vizuāli
šādu ŠA uzvedību laikā var novērot pēc norādes [10].
10
Attēls 2.13. Literatūrā izpētītie likumi uz 6-laukuma: (a) in, (b) Medium, (c) ick, (d) Golay,
(e) Preston [10]
Toties šādu ŠA uzvedība nereducējas uz struktūru stabilizāciju — likumiem Golay un Preston ir
raksturīga sprādziena aīstība — tāpēc mūsu darbā mēs nebalstījāmies uz tām, bet gan patstāvīgi
meklējam tādus likumus, kas apmierinātu Konveja nosacījumus (skat. sadaļu 2.3.2).
11
Nodaļa 3
Praktiskā daļa
Pamata metode, kas tika izmantota ŠA uzvedības analīzei 6-laukuma likumu izvēles posmā, bija EŠS
(šūna un tās kaimiņi) aīstības iznākumu analīze. Šī metode tika izmantota galvenokārt tādēļ, ka
likumi SD tiek definēti šūnas tiešai kaimiņniecībai. To arī var automatizēt darba efektivitātes uzlabošanai.
Izdevīga metodes īpašība ir arī neliels datu komplekta apjoms, kas raksturo dotu likumu, un
tā apstrādes ērtība. EŠS analīzē nav jāievēro laukuma specifika, jo pēc ŠA definīcijas šūnai vienmēr
ir noteikta kaimiņniecība. Beidzot, iznākumu analīze ļauj ar lielu precizitāti noteikt ŠA uzvedības
dinamiku uz PAL, jo tā uzskatāmi parāda stabilizācijas vai bezgalīgas aīstības tendences.
3.1 Modelēšana ar datora palīdzību
Pašā darba sākumā jau bija skaidrs, ka šādam ŠA modelēšanas un analīzes uzdevumam būs nepieciešama
datorlīdzekļu izmantošana, jo aprēķinu apjoms būs ļoti liels. Par galveno izmantoto programmēšanas
valodu mēs izvēlējamies P, jo mēs labāk pārzinām tās sintakses īpašības un FPC
kompilatoru [1].
Programmas rakstīšana notika paralēla vispārīgai ŠA pētīšanai, kas palīdzēja optimizēt darba
gaitu. Programma tika rakstīta posmos, kam bija tādas priekšrocības, kā atkļūdošanas un versiju
kontroles ērtība, metodiskā testēšanas sistēma un loģiskā koda uzbūve.
Galvenus programmas rakstīšanas posmus varētu izdalīt šādi:
1. nostādījums, pamata programmas struktūras plānojums;
2. laukuma EŠS ģenerēšana, ŠA aīstības modelēšana uz 4-laukuma, analītiska aparāta veidošana
un EŠS aīstības datu komplekta iegūšana, laukuma vizuālizatora veidošana;
3. darbs ar 6-laukumu — sešstūru laukuma izteikšana ar divdimensiju masīvu, visu likumu ģenerēšana,
visatbilstošāko likumu atlase, vizuālizatora modificēšana.
Tālāk mēs sīkāk aprakstīsim šos darba posmus un darba procesā iegūtos rezultātus.
Izveidotai programmai tika izvirzītas sekojošas prasības:
• programmai ir jāmodelē ŠA aīstība uz 4-laukuma un 6-laukuma;
• programmā ir jāiekļauj analītiskie elementi ŠA aīstības stāvokļa iegūšanai;
• programmai ir jānodrošina pietiekama funkcionalitāte ŠA likumu veidošanai un analīzei uz
n-laukuma, īpaši ja n = 6.
12
Attēls 3.2. (a) Toroidālais un (b) galīgais četrstūru laukumi
0
0
0
1 1
1
1 1
1
0 1 2
1
2
0
(a) (b)
Attēls 3.1. EŠS ieraksts programmā
Par ŠA uz 4-laukuma stāvokļa datu uzglabāšanas un apstrādes
pamata veidu tika izvēlēts trīsdimensiju binārais datu
masīvs, kur katrs elements ar koordinātēm (x; y; t) uzglabā informāciju
par šūnas, kura atrodas telpiskās koordinātēs x un y
paaudzē t, stāvokli. Mums ērtāks likās modelis, kurā laukums
ir izteikts kā šūnu masīvs ar dotajām koordinātēm. Piemēram,
EŠS, kas ir parādīta a. 3.1a, būs izteikta ar 2 2 divdimensiju
masīvu kā parādīts a. 3.1b.
Tā kā EŠS izmēri pēc x un y ass ir nepāra skaitļi, mēs noteicām centrālajai šūnai koordinātes
(0; 0). Šāda adresācija atvieglo darbu ar šūnas kaimiņiem programmā, kā arī ir intuitīvi saprotama
cilvēkiem.
Ir nepieciešams pieminēt, ka mūsu darbā mēs izmantojām nevis toroidālu laukumu (a. 3.2a), bet
plakanu un galīgu laukumu (a. 3.2b). Šāds lēmums varēja ietekmēt pētījuma rezultātus (struktūras
sasniegtu laukuma robežu un uzvestos neparedzami, jo šādā gadījumā malējām šūnām ir 3 vai 5
kaimiņi, nevis 8). Tomēr sekojošā analīze parādīja, ka savas aīstības gaitā EŠS sasniedz 100 100
liela laukuma malu tikai gadījumā, ja tā ir planieris vai veido planierus aīstības laikā (sīkāk par
planieriem skat. sadaļu 2.3.2).
Trešā dimensija masīvā ļauj apskatīt ŠA aīstības dinamiku. Katrs nākamais laika slānis ir jauna
ŠA paaudze, kuras stāvoklis tiek viennozīmīgi noteikts pēc ŠA likumiem balstoties uz iepriekšēja
slāņa stāvokli (a. 3.3, laika ass ir vērsta vertikāli).
Nākamais solis pie gatavas ŠA modeles izveides un pētījuma posms bija visu pirmās kārtas EŠS
ģenerēšana uz 4-laukuma. Vispār eksistē 2(N+1)2 atšķirīgo bināro apakšmatricu x 2
[
N
2 ; N
2
]
; y 2
[
N
2 ; N
2
]
. EŠS kārta P tiek izteikta ar formulu P = N1
2 , kur N 1 mod 2. Līdz ar to, ja P = 1,
tad N = 3. Var secināt, ka pirmās kārtas EŠS skaits ir 29 = 512. Visu šo apakšmatricu ģenerēšanai
mēs tās izteicām ar N2 elementu virknēm, kuru vērtības tika noteiktas izdrukas A.1 rindiņās
145–151, kur Max ir apskatāmo šūnu skaits (pirmās kārtas EŠS uz 4-laukuma Max = N2) un
PermutationNum = 2Max.
Koda darbības mehānisms ir sekojošs. No binārās skaitļa i formas mēs atgriežam j-to bitu, iz-
13
Attēls 3.3. Četrstūru laukuma aēlojums pa laika slāņiem
mantojot skaitļa i bitu pārbīdi pa labi uz j pozīcijām un tās disjunkciju ar 1, tad ierakstam to failā.
Faktiski, analoģiska ir skaitļa i bināras formas ierakstīšana failā, bet mēs to apgriezām, jo tas būtiski
neietekmē tālāko pētījumu.
Iegūto virkni mēs ierakstam atbilstošā EŠS no kreisās uz labo pusi, no augšas uz apakšu (divdimensiju
masīvu numerācija P valodā ir tieši tāda), iegūstot gatavu EŠS nulto iterāciju.
Darbojoties ar katru ģenerēto EŠS pēc kārtas, nākamajā solī mēs modelējam tās aīstību galīgā
iterāciju skaitā. Nākamā ŠA stāvokļa aprēķināšana ir triviāla — mēs “apejam” laika slāni no kreisās
uz labo pusi, no augšas uz apakšu, pārbaudot dzīvo kaimiņu skaitu telpiskajās koordinātēs atbilstošai
šūnai iepriekšējā laika slānī. Lai neievestu papildus pārbaudes, vai šūna ir laukuma malā, mēs
palielinājām masīvu pa divām šūnām — tādēļ mums nebija nepieciešamības pārbaudīt, vai šūnai ir
8 kaimiņi. Visām papildus šūnām ir stāvoklis 0 un tie nevar to izmainīt nekādā gadījumā.
Kad mums bija gatavs EŠS aīstības simulators pēc noteiktā iterāciju skaita, mēs uzsākām analītiskā
aparāta izstrādi. Mūsu mērķis bija tāda analīzes instrumenta veidošana, kas varētu noteikt 4
pamata ŠA stāvokļus:
• aīstības struktūra;
• oscilējošā struktūra;
• stabilā struktūra (oscilators ar periodu 1);
• bezgalīgās aīstības struktūra.
Oscilējošo struktūru pārbaudes mehānisms ir sekojošs: katrā iterācijā laukuma stāvoklis tiek salīdzināts
ar katru no n iepriekšējiem stāvokļiem, kur n ir pārbaudes dziļums. Testēšanas gaitā bija
noteikts, ka maksimālais efektīvais pārbaudes dziļums SD struktūrām, kas aīstās no pirmās kārtas
EŠS, ir 2, jo tieši tāds maksimālais oscilēšanas periods var būt iegūtajām periodiskajām nekustīgajām
struktūrām.
14
Attēls 3.4. EŠS planieri
Pār aīstības stāvokļiem tiek uzskatīti stāvokļi, kuros pēdējā aprēķinātajā paaudzē uz laukuma
ir dzīvas šūnas, kas nav nedz oscilējošas, nedz stabilās struktūras.
Galvenā grūtība, ar kuru mēs sastapāmies šajā darba posmā, bija noteikt, vai ŠA aīstīsies bezgalīgi
ilgi. Tā kā kustīgo struktūru noteikšana uz laukuma ir grūts process, mēs ieviesām atviegloto
pārbaudi. Ja malējām šūnām ir dzīvi kaimiņi, tas tika izvadīts failā. Mainot laukuma izmērus un
iterāciju skaitu un analizējot izvaddatus, mēs noteicām, ka planieri ir vienīgas kustīgas struktūras
kas rodas no EŠS 48 gadījumos no 512. Turpmākajai analīzei bija svarīgi noteikt, kādos konkrētajos
gadījumos tie rodas.
Planieris var būt pilnīgi ierakstīts EŠS. Tas var eksistēt divos atšķirīgos stāvokļos (a. 3.4, 1. rinda,
1. un 3. struktūra), katra no kurām ar pagriezienu un atspoguļojumu palīdzību var dot kopā astoņas
struktūras. Tādēļ 16 no 48 noteiktām struktūrām ir EŠS-planieri.
Toties rodas jautājums, kuras citas 32 EŠS veido planierus savas aīstības gaitā. Ir skaidrs, ka
jebkura asimetriska struktūra, kuru var ierakstīt 3 3 kvadrātā, var būt izteikta astoņos dažādos veidos,
tāpēc ir pietiekami atrast četras unikālas asimetriskas EŠS, kuras aīstības laikā veido planierus.
Analizējot izvaddatus un izmantojot vizuālizatoru, mēs izpētījām katru no mūs interesējošām 48 EŠS
un ieguvām sekojošus rezultātus:
• 16 struktūras — EŠS-planieri (a. 3.4);
• 8 struktūras kļūst par planieriem pirmajā paaudzē (a. 3.5a);
• 8 struktūras – “R” pentamino (struktūra, kas stabilizējas pēc 1103 iterācijām), no kuriem rodas
oscilējošas struktūras un seši planieri (a. 3.5b);
• 8 struktūras kļūst par “R” pentamino pirmajā paaudzē (a. 3.5c);
• 8 struktūras kļūst par “R” pentamino otrajā paaudzē (a. 3.5d).
Ir arī jāpiemin grūtības, kas bija radušās, mēģinot modelēt augstāko kārtu EŠS aīstību un analizējot
tās. Ja visu pirmās kārtas EŠS aīstības modelēšana aizņem 29N mašīnlaika (N ir vidējais
mašīnlaiks, nepieciešamais lai modelētu vienas EŠS aīstību), tad otras kārtas EŠS ir nepieciešams
jau 225N mašīnlaika (t / 2(2p+1)2 , p ir EŠS kārta). Novērtējot vidējo programmas darbības laiku
15
(a) (b) (c) (d)
Attēls 3.5. Struktūras, kuras pēc vienas vai vairākām paaudzēm ģenerē planierus. Sagrupētās struktūras
ir identiskās ar precizitāti līdz atspoguļošanai un pagriezieniem pa 90°.
X- 1 , - 1\
X- 1 , 0\
X- 1 , 1\
X 0 , - 1\
X 0 , 0\
X 0 , 1\
X 1 , - 1\
X 1 , 0\
X 1 , 1\
X- 1 , - 1\
X- 1 , 0\
X- 1 , 1\
X 0 , - 1\
X 0 , 0\
X 0 , 1\
X 1 , - 1\
X 1 , 0\
X 1 , 1\
Attēls 3.6. Laukuma transformēšana no sešstūra formas uz
četrstūra formu
Attēls 3.7. 6-laukuma vizuālizēšana
programmā
uz 2.6 GHz procesora ar 40 sekundēm uz 100 100 laukuma un maksimālo iterāciju skaitu 200, tie
paši aprēķini otras kārtas EŠS aizņem apmēram 30 dienas. Reāli šis laiks ir mazāks, jo programmā
ir paredzēta modelēšanas apstādināšana, ja struktūra nomirst vai kļūst par oscilatoru, un ātri mirstošo
struktūru īpatsvars starp otras kārtas EŠS ir lielāks. Mēs arī sastapāmies ar tādām problēmām,
kā datu tipu optimizācija lielu vērtību uzglabāšanai, izvaddatu analīzes grūtība un paralēlaprēķinu
nepieciešamība, tāpēc galvenokārt pētījums tika veikts ar pirmās kārtas EŠS.
Laukuma stāvokļu vērošanas atvieglošanai un uzskatāmībai mēs izveidojam laukuma stāvokļu
vizuālizatoru, izmantojot P grafisku moduli Graph. Uz laukuma mēs aēlojam dzīvas šūnas
ar baltu krāsu un mirušas ar melnu krāsu (tālāk tekstā ekrānuzņēmumi ir invertēti). Vizualizācijas
režīmā lietotājam ir pieejami modelējamās EŠS un iterācijas kārtas numurs. Kods ir viegli modificējams
lai izmainītu aizturi līdz paaudzes nomainīšanās uz ekrāna vai lietotāja un programmas
mijiedarbības īpašības.
Pēc tam, kad mēs ieguvām pilno datu komplektu par visu EŠS aīstības iznākumiem SD, mēs pārgājām
pie 6-laukuma izteikšanas, balstoties uz jau eksistējošo kodu un nemainot to radikāli. Mūsu
metode bija sekojoša. Uz laukuma ieviešam periodisku režģi, kas tiek noteikts ar diviem vienādiem
pēc moduļa bāzes vektoriem, kas ir vērsti savstarpēji perpendikulāri 4-laukumam un 60° leņķī 6-
16
laukumam. Katra kvadrāta vai sešstūra šūna var būt identificēta ar šāda režģa mezglu, un, aiecīgi,
var būt uzdota ar (a; b) koordinātēm ieviestajā bāzē. Šāda pieeja atvieglo informācijas par 6-laukumu
pārnešanu Pa masīvā: katras šūnas ar koordinātēm (a; b) stāvoklis viennozīmīgi atbilst [a; b]
masīva elementa stāvoklim. Šādu atbilstību 6-laukumam ilustrē a. 3.6.
Līdz ar to ŠA aīstības modelēšana uz 6-laukuma principiāli neatšķiras no ŠA aīstības modelēšanas
uz 4-laukuma. Analītisko aparātu modificēt nebija nepieciešams, jo laukuma aīstības, oscilācijas
un nāves stāvokļi tiek definēti analoģiski kā SD. 6-laukuma vizuālizators, savukārt, nedaudz
atšķirās no 4-laukuma vizuālizatora. Tā kā pierastā sešstūru režģa izvadīšana uz ekrānu bija problemātiska
ierobežo moduļa Graph iespēju dēļ, tika pieņemts lēmums izvadīt katru nākamo kolonnu
pārbīdītu par pusšūnu uz augšu aiecībā pret iepriekšējo (a 3.7).
3.2 Matemātiskā likumu meklēšana
Darbā izvirzītās problēmas atrisinājumam var izmantot vairākas metodes. Viena no tām balstās
uz šūnas stāvokļa izmaiņas varbūtību salīdzināšanu SD un katram no iespējamiem totalistiskajiem
likumiem ŠA uz 6-laukuma. Ja šīs varbūtības būs tuvas, tad var cerēt, ka arī vispārīgā uzvedība šiem
ŠA salīdzinājumā ar SD būs līdzīga.
SD pāreja 0 ! 1 notiek, kad šūnai ir trīs dzīvi kaimiņi. Kopā šūnai ir astoņi kaimiņi. Tas nozīmē,
ka šī pāreja notiks C38
gadījumos. Tā kā mēs apskatam tikai EŠS, tad šādas pārejas varbūtība ir
C38
28 = 0:21875: (3.1)
Pāreja 1 ! 1 notiek, kad šūnai ir divi vai trīs dzīvi kaimiņi, tātad tās varbūtība ir
C38
+ C28
28 = 0:328125: (3.2)
Mēs neapskatām pārejas 0 ! 0 un 1 ! 0, jo to varbūtības ir atkarīgas no apskatāmo pāreju varbūtībām,
jo abu pāreju ar vienādu sākuma stāvokli varbūtības summa ir viens.
6-laukumam mums ir zināms kopējais kaimiņu skaits — seši. Tātad kopējais šūnu izvietojumu
skaits ap centrālo šūnu ar zināmo stāvokli ir 26. Pēc mūsu pieņēmuma, lai ŠA uz 6-laukuma uzvestos
līdzīgi SD, atbilstošo pāreju varbūtību SD un 6-laukumam starpības modulim jābūt vismazākajam.
No šī pieņēmuma pārejai 0 ! 1 mēs iegūstam vienādību
1
26
Σk
i=1
Cxi
6 =
C38
28 = 0:21875 (3.3)
un pārejai 1 ! 1, aiecīgi
1
26
Σk
i=1
Cxi
6 =
C38
+ C28
28 = 0:328125 (3.4)
kur xi ir dzīvu kaimiņu daudzums. Tā kā šim vienādojumam nav atrisinājuma (izņemot kādus īpašus
gadījumus), mēs, piešķirot xi dažādas vērtības, aprēķinājām varbūtības un salīdzinājām tās ar
17
Tabula 3.1
Nepieciešamais šūnas kaimiņu daudzums, lai pāreju 0 ! 1 un 1 ! 1 varbūtības būtu tuvas
attiecīgajām varbūtībām SD
x1 x2 x3
1
26
Σk
i=1 Cxi
6
1
28 C38
1
28 (C38
+ C28
)
1(5) — — 0.093750
0.218750 0.328125
2(4) — — 0.234375
3 — — 0.312500
1(5) 2(4) — 0.328125
2(4) 3 — 0.546875
1(5) 3 — 0.406250
1 5 — 0.187500
1(5) 2(4) 3 0.640625
varbūtībām no SD. Dati ir apkopoti tabulā 3.1.
Ņemt vairāk par trim xi vērtībām nav jēgas, jo varbūtība tikai palielināsies, bet jau pie trim x
vērtībām tā ir lielāka par vistuvāko (treknrakstā: zilā krāsā 0 ! 1 pārejai, zaļā krāsā 1 ! 1 pārejai).
Tā kā Cn
m = Cmn
m , tad, piemēram, varbūtība pie x = 1 būs vienāda ar varbūtību pie x = 5, kas ir
ņemts vērā apaļās iekavās.
Spriežot pēc tabulas, pāreja 1 ! 1 notiek, kad šūnai ir vai nu divi, vai nu četri dzīvie kaimiņi;
pāreja 0 ! 1 notiek, kad šūnai ir vai nu viens un divi, vai nu viens un četri, vai nu divi
un pieci, vai nu četri un pieci kaimiņi. Līdz ar to mēs iegūstam astoņus likumus: 110000|010000,
100100|010000, 010010|010000, 000110|010000, 110000|000100, 010010|000010, 010010|000100,
000110|000100 (par likumu kodēšanu skat. sadaļu 3.3).
3.3 Likumu meklēšana ar datora palīdzību
Lai apstiprinātu vai noliegtu matemātiskos pieņēmumus par vistuvākajiem SD likumiem ŠA uz 6-
laukuma, izmantojot EŠS aīstības iznākumu analīzi, mēs nolēmām realizēt likumu ģeneratoru. Tas
ir aparāts, kas veido visus iespējamus likumus šūnas tiešai kaimiņniecībai totalistiskajā ŠA uz N-
laukuma. Izmantojot to, mēs varējam modelēt visu EŠS aīstību pēc katra likuma, un apkopojot
informāciju par iznākumiem, atrast statistiski visatbilstošāko SD likumu komplektu uz 6-laukuma.
Likumu ģenerēšanas princips ir līdzīgs EŠS ģenerēšanai. N-laukumam, mēs ģenerējam 2M simbolu
virkni, kas satur tikai simbolus 1 un 0. Šeit M ir visu pirmās kārtas kaimiņu skaits (ievērot
kaimiņu skaitu 0 nav jēgas, jo ar šādu nosacījumu 0 ! 1 pārejai visa laukuma tukša daļa momentāni
kļūst dzīva). Pirmie M simboli apraksta, kas notiek ar dzīvu šūnu nākamajā paaudzē (ja n-tais
virknes elements ir 1, tad šūna arī paliks dzīva pie n dzīviem kaimiņiem, ja 0 — tad nomirs pie
n dzīviem kaimiņiem). Nākamie M simboli analoģiski apraksta mirušas šūnas uzvedību nākamajā
paaudzē. Piemēram, likums 6-laukumam, pie kura dzīva šūna nākamajā paaudzē paliek dzīva,
ja tai ir divi vai trīs dzīvi kaimiņi, un miruša kļūst dzīva, ja tai ir 2 dzīvi kaimiņi, izskatīsies kā
011000|010000. Mēs ģenerējam 22M šādu virkņu, programmas izpildes laikā sadalām katru no tām
divos bināros viendimensiju masīvos, kur pirmais masīvs uzglabā pirmos M nosacījumus, otrais —
nākamos M nosacījumus. Ar katru iegūto likumu modelējam visu EŠS aīstību.
18
Izvaddatu faila fragments ir parādīts izdrukā 3.1, kur R ir likumu kodi, D, O, S, G, E ir atbilstoši
ŠA nāves, oscilējošo struktūru, stabīlu struktūru, laukuma malas sasniegšanas un aīstības pēdējā
iterācijā stāvokļu relatīvais biežums.
Izdruka 3.1: Likumu statistika
1 R 011100001000
2 D 0.6172
3 O 0.0156
4 S 0.3672
5 G 0.0000
6 E 0.0000
7 ...
8 R 011110000001
9 D 0.6328
10 O 0.0156
11 S 0.3516
12 G 0.0000
13 E 0.0000
To, cik tuvs pētītais likums ir SD var noteikt, izmantojot vairākas metodes. Šajā gadījumā mēs
darbojāmies sekojoši. No katra iespējama iznākuma pēc T iterācijām realizācijas varbūtībām fPig
tika sastādīts vektors h = ⟨PD; PO; PS; PG; PE⟩ 5-dimensiju iznākumu telpā. Analoģiskais vektors
l = ⟨P
D; P
O; P
S; P
G; P
E
⟩ tika sastādīts priekš SD likuma uz četrstūra laukuma. Par pētīta likuma
tuvuma mēru SD likumam mēs uzskatījām vektoru h un l starpības normas kvadrātu (salīdz. [31]).
2 = ∥h l∥2 =
Σ
i2fD;O;S;G;Eg
(Pi P
i )2: (3.5)
Šādā gadījumā jo 2 ir tuvāks nullei, jo labāka ir atbilstība starp pētīto un SD likumu.
Pārbaudei mēs izmantojām laukumu ar izmēru 100 100 un maksimālo iterāciju skaitu T =
200. Šāda parametru izvēle ļauj SD analīzē reģistrēt noteiktu katra no iznākumiem daudzumu (EŠS
planieri paspēj nonākt līdz laukuma robežai, bet planieri, kas ir radušies no citām struktūrām to
vēl nepaspēj izdarīt). Izdrukā 3.2 ir parādīti dati par SD aīstības iznākumu statistiku no visām
iespējamām EŠS konfigurācijām.
Izdruka 3.2: SD statistika
1 FIELD SIZE 100x100
2 ITERATION COUNT 200
3 Rule 0110000000100000
4 D 0.5137
5 O 0.1191
6 S 0.2734
7 G 0.0469
8 E 0.0469
6-laukuma likumu sakārtošanas procedūru pēc 2 mēs realizējām kā programmu Pythonā (izdruka
A.2), jo šī valoda ļauj ātri un vienkārši darboties ar kārtošanu un tekstu apstrādi. Pēc rezultātu
apkopošanas mēs ieguvām sakārtotu sarakstu ar likumiem, kas vislabāk atbilst SD iepriekš definētajā
nozīmē. Tālāk atlasītie likumi tika pielietoti EŠS un PAL aīstības pētīšanai (skat. sadaļu 3.4).
19
Pētīšana iekļāva sevī EŠS aīstības gaitas pēc uzdotiem likumiem stabilu un nestabilu struktūru
analīzi, kā arī vispārīgu ŠA uzvedības novērtējumu. Lai paveiktu pēdējo, mēs patvaļīgi aizpildījām
visas laukuma šūnas ar uzdotu vidēju dzīvu šūnu aizpildījuma blīvumu.
Mēs paveicām detalizētu EŠS un PAL aīstības dinamikas analīzi pie likumiem, kas ir vistuvāk
SD pēc aīstības iznākumu sadalījuma, kā arī klasificējām pie dotiem likumiem biežāk sastopamas
struktūras. PAL analīze galvenokārt tika veikta, pamatojoties uz struktūru stabilizācijas īpatnībām.
ŠA aīstības pie dotiem likumiem atbilstība SD arī tika noteikta, izmantojot šo parametru, tā kā tas
ir viens no galvenām Konveja izvirzītām prasībām priekš SD (skat. sadaļu 2.3.2).
3.4 Likumu analīze
Lai parādītu tās likumsakarības un īpašības, kuras ir kopīgas dažādiem likumiem, mēs nolēmām
izanalizēt pirmos septiņus likumus, kuri bija aprēķināti ar programmas palīdzību (tālāk programmas
likumi) un visus astoņus matemātiski aprēķinātus likumus (tālāk — matemātiskie likumi).
Pēc primāras analīzes, mums atkrita četri matemātiskie likumi, tā kā trijos no tiem (110000|010000,
100100|010000, 010010|010000) EŠS rezultāts bija bezgalīga aīstība, bet, izmantojot likumu 000110|
000100 uz PAL, visas šūnas mira pat pie dažādiem aizpildījuma blīvumiem (no 4 % līdz 50 %).
Analizējot programmas likumus mēs pamanījām, ka likumus var sadalīt divās grupās:
1. Pirmās grupas likumos šūna paliek dzīvā, kad tai ir viens dzīvs kaimiņš, un mirst, kad tai ir
divi dzīvie kaimiņi (10****|******);
2. Otrās grupas likumos šūna paliek dzīva, kad tai ir divi dzīvie kaimiņi, un mirst, kad tai ir viens
dzīvs kaimiņš (01****|******).
Šīs grupas atšķiras ar raksturīgajām stabilajām struktūrām un oscilatoriem, kuri rodas, izmantojot
pirmās vai otrās grupas likumus. Pirmās grupas likumos rodas salīdzinoši maza izmēra oscilatori
(kopējais dzīvo šūnu skaits — no diviem līdz četriem); otrās grupas likumos oscilatori ir lielāki (kopējais
dzīvo šūnu skaits — no trim līdz sešiem).
Mēs konstatējam, ka matemātiskiem likumiem šo likumsakarību arī daļēji var pielietot: no tabulām
B.1 un B.2 pielikumā B ir redzams, ka likumos 100100|000100 un 010010|000100 rodas raksturīgas
atbilstošai grupai oscilatori, bet likumā 110000|000100 rodas oscilatori no abām grupām.
Bet tomēr, mēs konstatējam, ka pārējie parametri (t. i. stabilizēšanas ātrums, oscilatoru īpašības),
kas raksturo ŠA uzvedību EŠS piemērā gan programmas, gan matemātiskajos likumos ir līdzīgas:
nestabilajai EŠS dzīvības ilgums ir viena vai divas iterācijas, retāk — trīs vai četras; oscilatora periods
visbiežāk ir viens, retāk divi vai trīs; ja sākuma EŠS pārvēršas oscilatorā, tad tas notiek pēc vienas
iterācijas, retāk — pēc divām.
Kad mēs apskatām PAL, no tabulas B.3 (skat. pielikumu B) ir redzams, ka mūsu likumu klasifikācija
ir pielietojama arī šeit. Pirmās grupas likumiem uz laukuma paliks vairāk stabilo struktūru
vai oscilatoru, nekā otrās grupas likumiem.
Bet šiem likumiem ir arī kopīgas pazīmes. Abu likumu grupu stabilizācijas ātrums ir liels (tab. B.3).
Stabilizācijas laiks palielinās ar PAL blīvuma palielināšanu, jo rodas atsevišķās struktūras, kurām ir
20
Attēls 3.8. (a) Logs un (b–e) Logu veida struktūras. Likumi 011000|0011*1. Oscilatoriem ir parādītas
visas konfigurācijas.
Attēls 3.9. Stabilizējušās struktūras uz PAL ar dažādu aizpildījuma blīvumu, ko norāda skaitļi (%)
Attēls 3.10. Pilsētu aīstība laikā. Skaitļi norāda uz iterācijas kārtas numuru.
21
lielāks stabilizācijas laiks (iterāciju daudzums pirms pārvēršanās oscilatorā vai pirms nāves). Ir svarīgi
atzīmēt, ka PAL, kuru blīvums ir mazāks par 20 %, galvenokārt jau pēc pirmās iterācijas “sadalās”
atsevišķajās struktūrās, kuri tālāk nemijiedarbojas.
Patvaļīgi aizpildot laukumu, gan programmas, gan matemātiskajos likumos galvenokārt rodas
oscilatori, kas kopē EŠS formu. Izņēmums ir otrās grupas likumi ar PAL blīvumu vairāk par 10 %. Likumos
011000|001111 un 011000|001101 rodas struktūras, kas ir līdzīgas logam (a. 3.8b–e). Kā redzams,
viena struktūra uzvedas diezgan interesanti. Struktūras, kuras rodas likumos 011100|001111
un 011100|001101, apskatīsim atsevišķi.
Šo struktūru īpašības ir daudz labāk redzamas, kad PAL aizpildījuma blīvums ir 20 % (salīdz.
a. 3.9). Visinteresantākais ir tas, ka šādām struktūrām ir fiksēts noslēgts perimetrs, līdz ar ko mēs
tās nosaucām par pilsētām. Tās var apvienoties (a. 3.10), un, kad viena struktūra pieskaras otrai,
jaunā struktūra tiecās izveidot gludu malu, palielinot savu laukumu. Turklāt struktūras iekšienē
notiek oscilācija, ko ir viegli novērot.
No tabulas B.2 ir redzams, ka matemātiskajos likumos ir neliela struktūru daudzveidība. Apskatot
PAL mēs arī nepamanījām nekā jauna vai neparasta. Bet atsevišķi jāapskata matemātisko likumu
000110|010000. Šim likumam ir unikālas īpašības. Pirmkārt, EŠS oscilatoriem ir lielāks periods (līdz
četrām iterācijām, tab. B.4), vidējais dzīves ilgums EŠS ir lielāks, PAL stabilizēšana ir daudz lēnāka
(tab. B.3). Ar lielāko PAL aizpildījuma blīvumu var novērot lielākos oscilatorus. Bet šo likumu
trūkums ir tas, ka tiem nav stabilo struktūru.
Salīdzinot ŠA uzvedību uz 6-laukuma ar iegūtiem likumiem un SD, jāatzīmē, ka visiem analizētiem
likumiem piemīt sekojošas īpašības: struktūrām nav haotiskās, bezgalīgās aīstības; visi PAL
laukumi stabilizējas, likumi ir vienkārši. Tomēr mums neizdevās atrast nelielas struktūras ar ilgu,
bet galīgu aīstību, kā arī mēs neatradām kustīgas struktūras.
22
Nodaļa 4
Secinājumi
1. Izvirzītā problēma ir daļēji atrisināta, jo mūsu atrastie likumi atbilst SD prasībām, bet mums
neizdevās tajos atrast kustīgas struktūras un nelielas struktūras ar ilgu aīstību.
2. Likumus 011100|001111 (šūna paliek dzīva, kad tai ir vai nu divi, vai nu trīs, vai nu četri dzīvie
kaimiņi; mirusī šūna pārvēršas par dzīvo, ja tai ir vai nu trīs, vai nu četri, vai nu pieci, vai nu
seši dzīvie kaimiņi) un 011100|001101 (šūna paliek dzīva, kad tai ir vai nu divi, vai nu trīs, vai
nu četri dzīvie kaimiņi; mirusī šūna pārvēršas par dzīvo, ja tai ir vai nu trīs, vai nu četri, vai nu
seši dzīvie kaimiņi) ir interesanti tālākajai pētīšanai, jo tajos pastāv struktūras ar nemainīgo
perimetru.
3. Likums 000110|010000 (šūna paliek dzīva, ja tai ir vai nu četri, vai nu pieci dzīvie kaimiņi;
šūna pārvēršas par dzīvo, ja tai ir divi dzīvie kaimiņi) atšķiras ar īpašībām no visiem pārējiem
pētītiem likumiem.
4. Likumus var klasificēt pēc viena vai dažiem nosacījumiem noteiktai pārejai un prognozēt ŠA
uzvedību neizpētītos likumos.
5. Tālākajiem precīzākajiem pētījumiem ir jāatrod jauni paņēmieni un metodes likumu analīzei
un salīdzināšanai.
23
Literatūra
[1] M. van Canneyt and F. Klämpfl. Free Pascal: User’s guide, December 2011.
[2] M. Cook. Universality in elementary cellular automata. Complex Systems, 15(1):1–40, 2004.
[3] Elementary cellular automaton. http://mathworld.wolfram.com/
ElementaryCellularAutomaton.html, 2012. Accessed 20/02/2012.
[4] A. Flammenkamp. Spontaneous appeared spaceships out of random dust. http://wwwhomes.
uni-bielefeld.de/achim/moving.html, 1995. Accessed 25/02/2012.
[5] A. Flammenkamp. Most seen Game-of-Life oscillators in the ash. http://wwwhomes.
uni-bielefeld.de/achim/freq_top_life.html, 2004. Accessed 25/02/2012.
[6] H. Fukś and N. Boccara. Generalized deterministic traffic rules. J. Modern Phys. C, 9(1):1–12,
1998.
[7] A. Gajardo, A. Moreira, and E. Goles. Complexity of Langton’s ant. Discr. Appl. Math.,
117(1):41–50, 2002.
[8] M. Gardner. e fantastic combinations of John Conway’s new solitaire game of “Life”. Scientific
American, 223, 1970.
[9] B. Grünbaum and G. C. Shephard. Tilings and paerns. W. H. Freeman & Company, 1987.
[10] Hexatron. A cellular automaton. http://www.hexatron.com/hexca/, 1999. Accessed
25/02/2012.
[11] D. Hickerson. Description of sliding block memory. http://www.radicaleye.com/lifepage/
patterns/sbm/sbm.html, 1990. Accessed 25/02/2012.
[12] O. Lafe. Data compression and encryption using cellular automata transforms. http://
lafenet.com/pdfs/cat_white_paper.pdf, 1997. Accessed 25/02/2012.
[13] C. G. Langton. Studying artificial life with cellular automata. Physica D, 22(1):120–149, 1986.
[14] Moore neighbourhood. http://mathworld.wolfram.com/MooreNeighborhood.html, 2012.
Accessed 25/02/2012.
[15] Mscibing. Universal constructor based spaceship. http://conwaylife.com/forums/
viewtopic.php?f=2&t=399, 18 May 2010. Accessed 25/02/2012.
[16] J. von Neumann. e general and logical theory of automata. In L. A. Jeffress, editor, Cerebral
Mechanisms in Behavior – e Hixon Symposium. John Willey & Sons, New York, 1951.
24
[17] von Neumann neighbourhood. http://mathworld.wolfram.com/vonNeumannNeighborhood.
html, 2012. Accessed 25/02/2012.
[18] R. Nobili and U. Pesavento. Generalized von Neumann’s automata I: A revisitation. In E. Besussi
and A. Cecchini, editors, Artificial Worlds and Urban Studies. DAEST Pubblication, Venezia,
1996.
[19] U. Pesavento. An implementation of von Neumann’s self-reproducing machine. Artificial Life,
2(4):337–354, 1995.
[20] J. M. Poutiers. Gastropods. In K. E. Carpenter, editor, e living marine resources of the Western
Central Pacific. FAO species identification guide for fishery purposes, volume 1. FAO, Rome, 1998.
[21] K. Preston, Jr. and M. J. B. Duff. Modern Cellular Automata. Plenum Press, New York, 1984.
[22] P. D. Reiners. Cellular automata and music. http://www.ibm.com/developerworks/java/
library/j-camusic/, 2004. Accessed 25/02/2012.
[23] R. Rucker. Examples. http://www.cs.sjsu.edu/faculty/rucker/capow/examples.html, 2006.
Accessed 25/02/2012.
[24] S. Ulam. Random processes and transformations. In International Congress of Mathematicians,
volume 2, Rhode Island, 1952. American Mathematical Society.
[25] N. Wiener and A. Rosenblueth. e mathematical formulation of the problem of conduction
of impulses in a network of connected excitable elements, specifically in cardiac muscle. Arch.
Inst. Cardiol. México, 16:205, 1946.
[26] Wolfram Mathematica 8 documentation, 2012. Random number generation.
[27] S. Wolfram. Statistical mechanics of cellular automata. Rev. Modern Phys., 55:601–644, 1983.
[28] S. Wolfram. A New Kind of Science. Wolfram Media Inc., 2002.
[29] M. J. Young. Typical uses of cellular automata. http://mjyonline.com/
CellularAutomataUses.htm, 2006. Accessed 25/02/2012.
[30] K. Zuse. Calculating space. Friedrich Vieweg & Sohn., Braunschweig, 1969. MIT technical
translation of 1970, Cambridge.
[31] Н. С. Бахвалов. Численные методы. Мир, Москва, 1973.
[32] Дж. фон Нейман. Теория самовоспроизводящихся автоматов. Мир, Москва, 1971.
[33] Т. Тоффоли and Н. Марголус. Машины клеточных автоматов. Мир, Москва, 1991.
25
Pielikums A
Datorprogrammu pirmkodi
Izdruka A.1: Pamatprogramma
1 { ********************************************************************
2 Program version for modelling and analysis of cellular automata
3 (CA) development on randomly f i l l e d f i e l d s with f i l l i n g density of
4 1/rdm in IterationCount iterations using the specific rule from f i l e
5 _rules . txt . The generator of rules i s commented out . The
6 generator of elementary c e l l structures cannot be removed , because
7 i t sets the number of i n i t i a l states we analyse . Graphical output
8 uses a delay of 0.05 s and user input i s required only in the very
9 end of CA development .
10 ******************************************************************** }
11
12 program ElementaryStructureAnalysis;
13 uses crt, wincrt, graph;
14
15 const N=6;
16 const ArrayBoundaries=-50;
17 const ArrayXSize=100;
18 const ArrayYSize=100;
19 const IterationCount=50;
20 const MaximumDepth=15;
21 const CellSizeMultiplier=6;
22 const Margin=10;
23 const rdm=10;
24
25 type MainArray = array [ArrayBoundaries-1..(ArrayBoundaries+ArrayXSize+1),
26 ArrayBoundaries-1..(ArrayBoundaries+ArrayYSize+1), 0..IterationCount] of boolean;
27 type RuleArray = array [1..N] of boolean;
28
29 var Max, PermutationNum, RuleNum: longint;
30 i, j, k, AliveNeighbours, InitialAlive, CheckDepth, OscDepth: longint;
31 // state check vars
32 IsAlive, StillLife, ToBreak, TempBreak, IsOsc, IsGlider: boolean;
33
34 main: MainArray;
35 AliveCountRule, DeadCountRule: RuleArray;
36
37 c, RowNum: longint;
38 ch: char;
39 TempStr: string [N*N];
40 TempRuleStr: string[80];
41
42 f, f_death, f_rulecheck, f_rules: text; // file vars
43
44 gd, gm: integer; // graph init vars
45
46 d, o, s, g, l: integer; // rulecheck vars
47 tempstring: string;
48
49 //********* FUNCTIONS AND PROCEDURES *********
50
51 function Power(a, b: longint):longint;
52 var i, base: longint;
53 begin
54 base:=a;
55 for i:=1 to (b-1) do base:=base*a;
56 Power:=base;
57 end;
58
59 procedure MatrixGraph(main: MainArray; iter: integer);
60 var i_m, j_m: integer;
61 tstr, tstr2: String[80];
62 begin
63 ClearViewPort;
64 Rectangle(Margin, Margin, ArrayXSize*(CellSizeMultiplier+2)+Margin,
65 ArrayYSize*CellSizeMultiplier+ArrayYSize*(CellSizeMultiplier div 2)+Margin);
66
67 SetFillStyle(SolidFill, 15);
68 SetLineStyle(0, 0, 1);
69 SetColor(7);
70
71 MoveTo(Margin, Margin);
72
73 // Visualising cell states
74 for i_m:=ArrayBoundaries-1 to ArrayBoundaries+ArrayXSize+1 do begin
75 for j_m:=ArrayBoundaries-1 to ArrayBoundaries+ArrayYSize+1 do begin
76 if main[i_m, j_m, iter]=TRUE then
77 Bar(GetX, GetY, GetX+CellSizeMultiplier, GetY+CellSizeMultiplier);
78 //line(GetX+(CellSizeMultiplier div 2),
79 //GetY, GetX+(CellSizeMultiplier div 2), GetY+600);
80 MoveTo(GetX, GetY+CellSizeMultiplier);
81 end;
82 if i_m<0 begin="" p="" then="">83 MoveTo(GetX+CellSizeMultiplier,
84 Margin+(CellSizeMultiplier div 2)*(ArrayXSize-i_m)-ArrayXSize);
85 line(GetX, GetY, GetX+CellSizeMultiplier, GetY+CellSizeMultiplier);
86 end
87 else if i_m>0 then begin
88 MoveTo(GetX+CellSizeMultiplier,
89 Margin+(CellSizeMultiplier div 2)*(ArrayXSize-i_m)-ArrayXSize);
90 line(GetX, GetY, GetX+CellSizeMultiplier, GetY+CellSizeMultiplier);
91 end
92 else if i_m=0 then MoveTo(GetX+CellSizeMultiplier,
93 Margin+(CellSizeMultiplier div 2)*ArrayXSize-ArrayXSize);
94 //if c=128 then readkey;
95 end;
96 OutTextXY((GetMaxX-GetMaxX div 3), (GetMaxY-50), 'Graph␣output␣successful');
97 tstr:='Rule␣#';
98 tstr:=tstr+TempRuleStr;
99 OutTextXY((GetMaxX-GetMaxX div 3), (GetMaxY-100), tstr);
100 tstr:='Iteration␣#';
101 str(iter, tstr2);
102 tstr:=tstr+tstr2;
103 OutTextXY((ArrayXSize*CellSizeMultiplier+Margin+300), (Margin+20), tstr);
104 tstr:='Permutation␣#';
105 str(c, tstr2);
106 tstr:=tstr+tstr2;
107 OutTextXY((ArrayXSize*CellSizeMultiplier+Margin+300), (Margin+40), tstr);
108 tstr:=tstr+tstr2;
109 delay(50);
110 end;
111
112 //********** MAIN BODY **********
113
114 begin
115 clrscr;
116 InitGraph(gd, gm, '');
117 ClearViewPort;
118
119 randomize;
120
121 PermutationNum:=Power(2, 7);
122 Max:=7;
123
124 assign(f, '_out.txt');
125 rewrite(f);
126 { assign ( f_rules , ’ _rules . txt ’ ) ;
127 rewrite ( f_rules ) ; }
128
129 assign(f_rulecheck, '_rulecheck.txt');
130 rewrite(f_rulecheck);
131 write(f_rulecheck, 'FIELD␣SIZE␣'); write(f_rulecheck, ArrayXSize);
132 write(f_rulecheck, 'x');
133 writeln(f_rulecheck, ArrayYSize);
134
135 write(f_rulecheck, 'ITERATION␣COUNT␣');
136 writeln(f_rulecheck, IterationCount);
137
138 write(f_rulecheck, 'OSCILLATOR␣DEPTH␣CHECK␣');
139 writeln(f_rulecheck, MaximumDepth);
140
141 writeln(f_rulecheck);
142
143 // ALGORHITM
144
145 // creating permutations of elementary structures
146 for i:=0 to (PermutationNum-1) do begin
147 for j:=0 to (Max-1) do begin
148 write(f, ((i shr j) and 1));
149 end;
150 writeln(f);
151 end;
152 close(f);
153
154
155
156 // creating rules
157 { RuleNum:=Power(2 , 12);
158 assign ( f_rules , ’ _rules . txt ’ ) ;
159 rewrite ( f_rules ) ;
160
161 for i :=0 to (RuleNum1) do begin
162 for j :=0 to 121 do begin
163 write ( f_rules , ( ( i shr j ) and 1 ) ) ;
164 end ;
165 writeln ( f_rules ) ;
166 end ;
167 close ( f_rules ) ; }
168
169 assign(f_rules, '_rules.txt');
170 reset(f_rules);
171
172 repeat
173
174 for i:=1 to 6 do begin
175 AliveCountRule[i]:=FALSE;
176 DeadCountRule[i]:=FALSE;
177 end;
178
179 readln(f_rules, TempRuleStr);
180
181 for i:=1 to 6 do
182 if TempRuleStr[i]='1' then AliveCountRule[i]:=TRUE;
183 for i:=1 to 6 do
184 if TempRuleStr[i+6]='1' then DeadCountRule[i]:=TRUE;
185
186 assign(f_death, '_death.txt');
187 rewrite(f_death);
188
189 assign(f, '_out.txt');
190 reset(f);
191
192 repeat
193 readln(f, TempStr);
194 inc(c);
195 InitialAlive:=0;
196
197 // filling the array with FALSE values
198 for i:=0 to IterationCount do begin
199 for j:=ArrayBoundaries-1 to (ArrayBoundaries+ArrayXSize+1) do begin
200 for k:=ArrayBoundaries-1 to(ArrayBoundaries+ArrayYSize+1) do
201 main[j, k, i]:=FALSE;
202 end;
203 end;
204
205 // assigning the original state of an elementary cell structure
206 { for i :=1 to N+1 do begin
207 i f TempStr[ i ]= ’0 ’ then begin
208 i f i=1 then main[1, 1, 0]:=FALSE;
209 i f i=2 then main[0 , 1, 0]:=FALSE;
210 i f i=3 then main[1, 0 , 0]:=FALSE;
211 i f i=4 then main[0 , 0 , 0]:=FALSE;
212 i f i=5 then main[1 , 0 , 0]:=FALSE;
213 i f i=6 then main[0 , 1 , 0]:=FALSE;
214 i f i=7 then main[1 , 1 , 0]:=FALSE;
215 end
216 else begin
217 i f i=1 then main[1, 1, 0]:=TRUE;
218 i f i=2 then main[0 , 1, 0]:=TRUE;
219 i f i=3 then main[1, 0 , 0]:=TRUE;
220 i f i=4 then main[0 , 0 , 0]:=TRUE;
221 i f i=5 then main[1 , 0 , 0]:=TRUE;
222 i f i=6 then main[0 , 1 , 0]:=TRUE;
223 i f i=7 then main[1 , 1 , 0]:=TRUE;
224 inc ( InitialAlive ) ;
225 end ;
226 end ; }
227
228 for i:=ArrayBoundaries to (ArrayBoundaries+ArrayXSize) do begin
229 for j:=ArrayBoundaries to (ArrayBoundaries+ArrayYSize) do begin
230 if random(rdm)=1 then main[i, j, 0]:=TRUE;
231 end;
232 end;
233
234 // printing out the result (testing purposes)
235 InitialAlive:=0;
236 for i:=0 to (N*N-1) do begin
237 if main[(-(N div 2)+(i mod N)),
238 (-(N div 2)+(i div N)), 0]=FALSE then write('0␣')
239 else begin
240 write('1␣');
241 inc(InitialAlive);
242 end;
243 if ((i+1) mod N)=0 then writeln;
244 end;
245
246 //MatrixGraph(main, 0);
247 //readkey;
248
249 //simulating the development of an elementary structure and
250 //analyzing every iteration state.
251 for i:=1 to IterationCount do begin
252
253 if InitialAlive=0 then begin
254 write(f_death, 'd␣');
255 writeln(f_death, i-1);
256 end;
257 if InitialAlive=0 then break;
258
259 IsAlive:=FALSE;
260 ToBreak:=FALSE;
261 StillLife:=TRUE;
262 IsOsc:=FALSE;
263
264 // calculating every cell`s state in i-th iteration
265
266 for j:=ArrayBoundaries to (ArrayBoundaries+ArrayXSize) do begin
267 for k:=ArrayBoundaries to (ArrayBoundaries+ArrayYSize) do begin
268 AliveNeighbours:=0;
269 case main[j, k, i-1] of
270 TRUE : begin
271 if main[j-1, k-1, i-1]=TRUE then inc(AliveNeighbours);
272 if main[j-1, k, i-1]=TRUE then inc(AliveNeighbours);
273 //if main[j-1, k+1, i-1]=TRUE then inc(AliveNeighbours);
274 if main[j, k-1, i-1]=TRUE then inc(AliveNeighbours);
275 if main[j, k+1, i-1]=TRUE then inc(AliveNeighbours);
276 //if main[j+1, k-1, i-1]=TRUE then inc(AliveNeighbours);
277 if main[j+1, k, i-1]=TRUE then inc(AliveNeighbours);
278 if main[j+1, k+1, i-1]=TRUE then inc(AliveNeighbours);
279
280 if AliveNeighbours=0 then main[j, k, i]:=FALSE
281 else if AliveCountRule[AliveNeighbours]<>TRUE
282 then main[j, k, i]:=FALSE;
283 if AliveNeighbours<>0 then begin
284 if AliveCountRule[AliveNeighbours]=TRUE then begin
285 IsAlive:=TRUE;
286 main[j, k, i]:=TRUE;
287 end;
288 end;
289 end;
290
291 FALSE : begin
292 if main[j-1, k-1, i-1]=TRUE then inc(AliveNeighbours);
293 if main[j-1, k, i-1]=TRUE then inc(AliveNeighbours);
294 //if main[j-1, k+1, i-1]=TRUE then inc(AliveNeighbours);
295 if main[j, k-1, i-1]=TRUE then inc(AliveNeighbours);
296 if main[j, k+1, i-1]=TRUE then inc(AliveNeighbours);
297 //if main[j+1, k-1, i-1]=TRUE then inc(AliveNeighbours);
298 if main[j+1, k, i-1]=TRUE then inc(AliveNeighbours);
299 if main[j+1, k+1, i-1]=TRUE then inc(AliveNeighbours);
300
301 if AliveNeighbours<>0 then begin
302 if DeadCountRule[AliveNeighbours]=TRUE then begin
303 main[j, k, i]:=TRUE;
304 IsAlive:=TRUE;
305 end;
306 end;
307 end;
308 end;
309 end;
310 end;
311
312 MatrixGraph(main, i);
313
314 // Checking for gliders or other moving formations.
315
316 { IsGlider :=FALSE;
317
318 for j :=ArrayBoundaries to ( ArrayBoundaries+ArrayXSize) do begin
319 i f main[ j , ArrayBoundaries , i1]=TRUE then IsGlider :=TRUE;
320 end ;
321
322 for j :=ArrayBoundaries to ( ArrayBoundaries+ArrayXSize) do begin
323 i f main[ j , ArrayBoundaries+ArrayYSize , i1]=TRUE then IsGlider :=TRUE;
324 end ;
325
326 for k:=ArrayBoundaries to ( ArrayBoundaries+ArrayYSize ) do begin
327 i f main[ArrayBoundaries , k , i1]=TRUE then IsGlider :=TRUE;
328 end ;
329
330 for k:=ArrayBoundaries to ( ArrayBoundaries+ArrayYSize ) do begin
331 i f main[ArrayBoundaries+ArrayXSize , k , i1]=TRUE then IsGlider :=TRUE;
332 end ;
333
334 i f IsGlider=TRUE then begin
335 / / readkey ;
336 write ( f_death , ’g ’ ) ;
337 writeln ( f_death , i1);
338 end ;
339 i f IsGlider=TRUE then break ; }
340
341 // Determining death of given structure, if is alive - continuing.
342
343 if IsAlive=FALSE then begin
344 write(f_death, 'd␣');
345 writeln(f_death, i);
346 //readkey;
347 end;
348 if IsAlive=FALSE then break;
349
350 if IsAlive=TRUE then begin
351 if i=IterationCount then begin
352 //readkey;
353 write(f_death, 'l␣');
354 writeln(f_death, IterationCount);
355 end;
356 end;
357
358 // Checking for still lifes and oscillators.
359
360 if IsAlive=TRUE then begin
361 for j:=ArrayBoundaries to (ArrayBoundaries+ArrayXSize) do begin
362 for k:=ArrayBoundaries to (ArrayBoundaries+ArrayYSize) do begin
363 if main[j, k, i]<>main[j, k, i-1] then StillLife:=FALSE;
364 end;
365 end;
366 end;
367
368 if StillLife=FALSE then begin
369 for CheckDepth:=2 to MaximumDepth do begin
370
371 if CheckDepth>i then break;
372 IsOsc:=TRUE; // !!
373 for j:=ArrayBoundaries to (ArrayBoundaries+ArrayXSize) do begin
374 for k:=ArrayBoundaries to (ArrayBoundaries+ArrayYSize) do begin
375 if (main[j, k, i]<>main[j, k, (i-CheckDepth)]) then IsOsc:=FALSE;
376 end;
377 end;
378
379 if IsOsc=TRUE then OscDepth:=CheckDepth;
380 if IsOsc=TRUE then break;
381 end;
382 end;
383
384 if StillLife=TRUE then begin
385 OutTextXY((GetMaxX-GetMaxX div 3), (GetMaxY-100), 'STILL␣LIFE␣!');
386 readkey;
387 ToBreak:=TRUE;
388 write(f_death, 's␣');
389 writeln(f_death, i-1);
390 end;
391 if IsOsc=TRUE then begin
392 readkey;
393 ToBreak:=TRUE;
394 write(f_death, 'o␣');
395 write(f_death, i-OscDepth);
396 write(f_death, '(');
397 write(f_death, OscDepth);
398 writeln(f_death, ')');
399 end;
400
401 if ToBreak=TRUE then break;
402
403 end;
404 writeln;
405
406 until EOF(f);
407
408 close(f_death);
409 close(f);
410
411 // RULECHECK
412 assign(f_death, '_death.txt');
413 reset(f_death);
414
415 write(f_rulecheck, 'R␣'); writeln(f_rulecheck, TempRuleStr);
416
417 d:=0; o:=0; s:=0; g:=0; l:=0;
418
419 repeat
420 readln(f_death, tempstring);
421 if (tempstring[1]='d') then inc(d);
422 if (tempstring[1]='o') then inc(o);
423 if (tempstring[1]='s') then inc(s);
424 if (tempstring[1]='g') then inc(g);
425 if (tempstring[1]='l') then inc(l);
426 until EOF(f_death);
427
428 write(f_rulecheck, 'D␣'); writeln(f_rulecheck, (d/Power(2, N+1)):1:4);
429 write(f_rulecheck, 'O␣'); writeln(f_rulecheck, (o/Power(2, N+1)):1:4);
430 write(f_rulecheck, 'S␣'); writeln(f_rulecheck, (s/Power(2, N+1)):1:4);
431 write(f_rulecheck, 'G␣'); writeln(f_rulecheck, (g/Power(2, N+1)):1:4);
432 write(f_rulecheck, 'D␣'); writeln(f_rulecheck, (l/Power(2, N+1)):1:4);
433
434 close(f_death);
435
436 until EOF(f_rules);
437
438 close(f_rulecheck);
439
440 CloseGraph;
441 end.
Izdruka A.2: Likumu šķirotajs
1 # ! / usr / bin / python2
2
3 # Define probabilities of different outcomes of Conway’ s Game of Life
4 # (CGoL) :
5 # r The code of the rule [ see Eq . ( 2 . 2 ) ]
6 # The tag ’ Life ’ i s reserved for the original set of rules
7 # d the l i f e dies away at the time step T <= Tmax
8 # o the l i f e o s c i l l a t e s between k stable configurations
9 # s the l i f e comes to a fixed point
10 # g the l i f e propagates in the timespace with fixed WW and KK
11 # e the l i f e exhibits infinite unperiodic developement
12
13 vecLife = ['Life', 0.5137, 0.1191, 0.2734, 0.0938, 0.0000]
14
15 def distance2(r, d, o, s, g, e):
16 ””” Returns a squared distance between the given vector and
17 the vector vecLife as defined in the general Euclid space ,
18 i . e . D^2 = | | V_1 V_2| | ^ 2 = Sum_i (V_1[ i ] V_2[ i ])^2.
19
20 The l e s s the squared distance is , the better the rule
21 considered matches the rule of the CGoL.
22 ”””
23 nLen = 5
24 vec = [d, o, s, g, e]
25 return reduce(lambda x, y: x + y,\
26 [(vec[-nLen:][i] - vecLife[-nLen:][i]) ** 2\
27 for i in range(nLen)])
28
29 # Reading the f i l e with the analysis of the rules
30 f = open('_rulecheck.txt', 'r')
31 data = [x.split()[1] for x in f.readlines()[4:]]
32 f.close()
33
34 # Forming data vectors in the form [ r , d , o , s , g , e ]
35 collatedData = []
36 for i in range(0, len(data), 6):
37 q = [float(data[i + j]) for j in range(1, 6)]
38 q[:0] = [data[i]]
39 collatedData.append(q)
40 del data, q
41
42 # Forming arrays in the form [ rule , | | Rule – GoL | | ² ]
43 ruleDist = [[q[0], distance2(*q)] for q in collatedData]
44
45 # Sorting and printing
46 for i in sorted(ruleDist, key=lambda rule: rule[1]):
47 print i[0], i[1]
Pielikums B
Datu tabulas
Tabula B.1
Oscilatori uz 6-laukuma. Kods 1 un 2 ir oscilatora 1. un 2. (ja tā periods ir 2) konfigurācijas
kodi, Attēls — oscilatora vizuālais noformējums mūsu programmā (oscilatoriem ar periodu 2 ir
parādītas abas konfigurācijas).
Nosaukums Kods 1 Kods 2 Attēls
Lielgabals 110 1 000
Alpinists 110 1 100
Teitonis 111 1 000
Pistole 111 1 100
Cepure 110 1 110
Termometrs 010 1 101 101 1 010
Logs 111 1 111 111 0 111
Līnija-1 110 0 000
Kronis 111 0 000 101 1 000
Cirvis 010 1 100 110 0 100
Līnija-2 011 0 110
Līnija-3 001 1 100
Vārti 011 0 110 110 1 011
Pakavs 111 0 011
Tanks 111 0 101
Tabula B.2
Oscilatoru un stabilo struktūru (O un S) izkārtojums uz 6-laukuma pa programmas likumiem
(pa kreisi) un matemātiskajiem likumiem (pa labi). Ar slīprakstu iezīmētām struktūrām
realizējas tikai pirmā no tab. B.1 norādītajām konfigurācijām.
Programmas likumi
Likums O un S
R 011100|001111
Lielgabals
Alpinists
Teitonis
Pistole
Cepure
Termometrs
Logs
R 011100|001101
Lielgabals
Alpinists
Teitonis
Pistole
Cepure
Termometrs
Logs
R 100010|001010
Līnija-1
Kronis
Cirvis
Līnija-2
R 100010|001000
Līnija-1
Kronis
Cirvis
Līnija-2
R 100010|001100
Līnija-1
Kronis
Cirvis
R 011000|001111
Lielgabals
Kronis
Alpinists
Logs
R 011000|001101
Lielgabals
Kronis
Alpinists
Logs
Matemātiskie likumi
Likums O un S
R 110000|000100
Līnija-1
Cirvis (1)
Lielgabals
Kronis
Logs
Līnija-3
Vārti
Pakavs
Tanks
R 100100|000100 Līnija-1
R 010010|000100
Lielgabals
Logs
Tabula B.3
Likumu statistika uz 6-laukuma. NOS ir oscilatoru un stabilo struktūru skaits (priekš EŠS) un
vidējais skaits (priekš PAL), Ts ir vidējais iterāciju skaits pirms laukuma stabilizēšanas.
Likums Starpība EŠS PAL aizpildījuma blīvums
4 % 5 % 7 % 10 %
NOS NOS Ts NOS Ts NOS Ts NOS Ts
R 011100|001111 0.0127 61 1.0 1.6 3.5 2.8 8.3 2.8 30.8 3.3
R 011100|001101 0.0129 55 1.6 2.0 3.1 2.6 10.1 3.0 30.6 3.4
R 100010|001010 0.0154 57 23.3 2.6 43.6 2.9 74.3 4.4 103.5 4.4
R 100010|001000 0.0172 51 29.5 2.4 38.7 2.8 70.6 4.1 111.7 4.7
R 100010|001100 0.0191 54 32.8 2.6 41.3 4.0 74.0 4.8 110.4 5.9
R 011000|001111 0.0195 61 0.8 2.2 2.9 2.6 11.4 5.1 29.4 7.0
R 011000|001101 0.0198 49 2.0 3.0 2.6 2.6 9.0 4.7 27.0 8.8
R 110000|000100 0.0690 70 33.5 1.4 61.0 3.2 65.8 3.9 180.6 5.8
R 100100|000100 0.0879 30 26.9 2.0 43.7 2.5 77.0 3.0 131.4 3.7
R 010010|000100 0.2004 13 0.8 1.9 1.4 2.0 5.3 2.6 11.6 3.4
R 000110|010000 0.2779 71 34.5 9.6 64.1 15.2 80.8 19.8 111.1 27.6
Tabula B.4
Oscilatori, kuri rodas, izmantojot likumu 000110|010000. Attēlā ir parādītas visas oscilatora
konfigurācijas.
Nosaukums Attēls
Ēna
Zalve
Izkapts
Sirpis
Portāls
Trijstūris
Pielikums C
Terminu vārdnīca
Binārais šūnu automāts — šūnu automāts, kurā katra šūna var atrasties tikai vienā no diviem stāvokļiem,
nosacīti — “dzīva” vai “miruša”.
Šūna — šūnu laukuma pamatvienība, kas var atrasties vienā no vairākiem stāvokļiem.
Struktūra — šūnu kopa, kurā šūnas mijiedarbojas.
Šūnu laukums — šūnu kopa, kurā katra no šūnām ir saistīta ar kādām citām šūnām, kuras, savukārt,
veido tās šūnas kaimiņniecību.
Šūnas n-tās kārtas kaimiņniecība — šūnu kopa, kurā katra no šūnām atrodas n saišu aālumā no
dotās šūnas (a. C.1).
4-laukums — šūnu laukuma paveids, kur katra šūna ir saistīta ar tiešo kaimiņniecību ar 8 citām
šūnām (Mūra kaimiņniecība, a. C.1)
6-laukums — šūnu laukuma paveids, kur katra šūna ir saistīta ar tiešo kaimiņniecību ar 6 citām
šūnām (a. C.2).
n-tās kārtas elementāra šūnu struktūra (EŠS) — šūna un visi tās kaimiņi līdz n-tas kārtas ieskaitot
uz tukša laukuma.
n-tā paaudze — laukuma stāvoklis pēc n reižu likuma pielietošanas laukuma struktūrām.
X-4, -4\
X-4, -3\
X-4, -2\
X-4, -1\
X-4, 0\
X-4, 1\
X-4, 2\
X-4, 3\
X-4, 4\
X-3, -4\
X-3, -3\
X-3, -2\
X-3, -1\
X-3, 0\
X-3, 1\
X-3, 2\
X-3, 3\
X-3, 4\
X-2, -4\
X-2, -3\
X-2, -2\
X-2, -1\
X-2, 0\
X-2, 1\
X-2, 2\
X-2, 3\
X-2, 4\
X-1, -4\
X-1, -3\
X-1, -2\
X-1, -1\
X-1, 0\
X-1, 1\
X-1, 2\
X-1, 3\
X-1, 4\
X0, -4\
X0, -3\
X0, -2\
X0, -1\
X0, 0\
X0, 1\
X0, 2\
X0, 3\
X0, 4\
X1, -4\
X1, -3\
X1, -2\
X1, -1\
X1, 0\
X1, 1\
X1, 2\
X1, 3\
X1, 4\
X2, -4\
X2, -3\
X2, -2\
X2, -1\
X2, 0\
X2, 1\
X2, 2\
X2, 3\
X2, 4\
X3, -4\
X3, -3\
X3, -2\
X3, -1\
X3, 0\
X3, 1\
X3, 2\
X3, 3\
X3, 4\
X4, -4\
X4, -3\
X4, -2\
X4, -1\
X4, 0\
X4, 1\
X4, 2\
X4, 3\
X4, 4\
y
x
Attēls C.1. 4-laukuma centrālā šūna un tās
1. un 2. kārtas kaimiņi. Katra
kaimiņniecība ir aizkrāsota ar citu
nokrāsu.
X- 4 , - 4 \
X- 4 , - 3\
X- 4 , - 2 \
X- 4 , - 1\
X- 4 , 0\
X- 4 , 1\
X- 4 , 2 \
X- 4 , 3\
X- 4 , 4 \
X- 3 , - 4 \
X- 3 , - 3\
X- 3 , - 2 \
X- 3 , - 1\
X- 3 , 0\
X- 3 , 1\
X- 3 , 2 \
X- 3 , 3\
X- 3 , 4 \
X- 2 , - 4 \
X- 2 , - 3\
X- 2 , - 2 \
X- 2 , - 1\
X- 2 , 0\
X- 2 , 1\
X- 2 , 2 \
X- 2 , 3\
X- 2 , 4 \
X- 1 , - 4 \
X- 1 , - 3\
X- 1 , - 2 \
X- 1 , - 1\
X- 1 , 0\
X- 1 , 1\
X- 1 , 2 \
X- 1 , 3\
X- 1 , 4 \
X 0 , - 4 \
X 0 , - 3\
X 0 , - 2 \
X 0 , - 1\
X 0 , 0\
X 0 , 1\
X 0 , 2 \
X 0 , 3\
X 0 , 4 \
X 1 , - 4 \
X 1 , - 3\
X 1 , - 2 \
X 1 , - 1\
X 1 , 0\
X 1 , 1\
X 1 , 2 \
X 1 , 3\
X 1 , 4 \
X 2 , - 4 \
X 2 , - 3\
X 2 , - 2 \
X 2 , - 1\
X 2 , 0\
X 2 , 1\
X 2 , 2 \
X 2 , 3\
X 2 , 4 \
X 3 , - 4 \
X 3 , - 3\
X 3 , - 2 \
X 3 , - 1\
X 3 , 0\
X 3 , 1\
X 3 , 2 \
X 3 , 3\
X 3 , 4 \
X 4 , - 4 \
X 4 , - 3\
X 4 , - 2 \
X 4 , - 1\
X 4 , 0\
X 4 , 1\
X 4 , 2 \
X 4 , 3\
X 4 , 4 \
b
a
Attēls C.2. 6-laukuma centrālā šūna un tās
1. un 2. kārtas kaimiņi. Katra
kaimiņniecība ir aizkrāsota ar citu
nokrāsu.
Nav komentāru:
Ierakstīt komentāru