Gramatika beskonačnog

“Molim vas, nacrtaj izračunaj mi ovcu”

Papratnjače (Ptaeridophyta) su stara porodica biljaka koje su caravale zemljom davno prije cvjetnica. Lijevo možemo vidjeti sliku primjerka karakterističnih osobina od kojih je najuočljiviji specifičan pravilni uzorak lista biljke.

Desno je još jedan primjerak, nepoznatog podrijetla. Vrsta koju vidimo na toj slici vezana je uz neobičnu legendu. Naime, priča kaže kako ova paprat u prirodi zapravo ne postoji. I ne samo to, ista legenda tvrdi kako je crtež te vrste nastao mukotrpnim radom jedne kornjače. Kako to da kornjača zna crtati? Zašto baš paprat? Tko može vjerovati da ovo na slici desno nije crtež stvarne paprati? Kakve veze to ima s fraktalima?

Upoznajte L-Sisteme

L-sistemi su matematički formalizam kojeg je 1968. izumio mađarski biolog Aristid Lindenmayer. Kao biolog, Lindermayer se bavio proučavanjem rasta i razvoja biljaka, algi i bakterija. Da bi mogao modelirati faze razvoja jedinke kao i povezanost susjednih i istovremenih događaja trebao mu je sustav koji omogućuje u svakom koraku istovremeno mijenjanje više osnovnih objekata. L-sistem je algoritam zamjene znakova u nekom znakovnom nizu. Osnovna ideja je da se počne od jednostavng skupa znakova, a zatim se iterativno svaki znak u skupu zamjenjuje složenijim skupom istih znakova. Npr. neka imamo početni niz “aabbbaaa” i pravilo koje svako ‘a’ zamjenjuje s “abb” i svako ‘b’ s “aa”. U prvom koraku krećemo od inicijalnog niza i primjenjujemo pravila na svaki znak te dobivamo: “abb abb aa aa aa abb abb abb abb”. Sljedeći korak je primjena istih pravila na dobiveni niz znakova u prethodnom koraku. Na taj način postiže se osnovna Lindermayerova ideja da se počevši od jednostavnog objekta i dodajući (umečući) mu druge jednostavne objekte kreira krajnji objekt promatranja. Ono što L-sisteme razlikuje od ostalih sličnih postupaka jest činjenica da se izmjene početng objekta dešavaju paralelno (u svakom koraku se radi više od jedne zamjene znakova) čime se postiže modeliranje bioloških procesa koji zbog svoje prirode zahtjevaju paralelizam. (Za formalnu definiciju L-sistema vidjeti članak na wikipediji)

Geometrija kornjače

Vrlo brzo nakon njihovog nastanka, predložena je i geometrijska interpretacija L-sistema. Jedna od njih postala je standardnom i danas je jedina koja se koristi. Dakle… Zamislimo kornjaču. Kornjača ima svoj položaj u 2D ravnini označen točkom . Isto tako linija koja se proteže od glave do repa naše beštije zatvara neki kut s osi , nazovimo ga . Stoga kornjaču određuje trojac . Definiraju se i dvije konstante: prijeđeni put (duljina linije) i povečanje kuta . Abeceda takvog L-sistema se sastoji od 4 znaka: sa sljedećim značenjem:

• F – Pomakni kornjaču iz trenutnog položaja u novi položaj pri čemu je i . Postavi kornjaču u novo stanje:
• f – isto kao F ali se samo mijenja stanje kornjače, bez de se prikaže linija.
• + – okreni kornjaču na lijevo za kut tako da je novi kut kornjače
• - – okreni kornjaču na desno za kut tako da je novi kut kornjače

(Napomena: Ovo je osnovna abeceda, za kompleksnije sisteme ovoj abecedi se dodaju još neki znakovi ali princip rada je isti…)

Kao kod svakog L-sistema sada se zadaju:

• aksiom – početni string. npr. “FFF–fff“
• početni kut i položaj kornjače
• pravila za prepisivanje, npr “F -> ff++FF”

Iteracijom zadanog L-sistema renderira se konačni objekt. E sad bi bilo vrijeme da odgovorim na barem neka pitanja postavljena na početku. Zašto baš kornjača? Razlozi su povijesni. Nekad davno postojao je jedan programski jezik u kojem ste imali kursor na ekranu i programirali njegovo pomicanje te tako stvarali sliku. Programski jezik se zvao LOGO a kursor je u prvim verzijama bio prikazan kao kornjača.

Papratnjnače, fraktali i jedan problem.

Uzevši da je korjen L-sistema u biologiji prva primjena koju su pronašli bila je u modeliranju bioloških struktura. Ubrzo su se pojavili programčići koji su mogli izgenerirati prvih nekoliko koraka itercije jednostavnijih L-sistema. Rezultati su bili zapanjujuči. Na ekranu su se pojavljivale slike neviđenih i nikad otkrivenih biljaka. Ipak, najveće zaprepaštenje izazvala je nevjerojatna sličnost “umjetnih” i stvarnih biljnih struktura. Drveće, lišće i cvijeće… Sve to bi proizašlo iz malih i jednostavnih jednadžbi. Ideja da jedna tako složena arhitektura kao što je list biljke može biti opisana jednostavnim nizom znakova ubrzo je postala ideja vodilja za istraživanje L-sistema. Danas su dva područja na kojima se oni istražuju. Prvo je modeliranje realističnih biljaka (dovedeno na sasvim novu razinu kad su se L-sistemi prebacili u 3 dimenzije). Vodeće ime na ovom području je prof. Przemyslaw Prusinkiewicz, voditelj “Biological Modeling and Visualization research group” na sveučilištu Calgary, Kanada. Njihove prekrasne radovi, uključujući i potpuno besplatan i za download dostupan klasik “Algorithmic beauty of nature” možete pronaći ovdje: Algorithmic Botany. Još jedan prekrasan prikaz što se sve može sa L-sistemima (gledano s umjetničkog aspekta) dostupan je ovdje Xenodream. Naravno, tu je i moj skromni doprinos istoj tematici: by El Gruñón…

Drugo važno područje istraživanja je (još uvijek otvoreno) pitanje pronalaženja odgovarajučeg L-sistema za zadanu strukturu ili proces. Naime, unatoč zapanjujučoj sličnosti, slike generirane L-sistemima nisu u potpunosti jednake pravim biljkama. Unatoč tom nedostatku, smatra se da je Lindenmayer uspio u svojoj namjeri, naime stvorio je sustav modeliranja koji omogućuje (za sada u ograničenom obliku) predviđanje grananja bioloških struktura. Ovaj problem ostaje otvoren ali i intenzivno proučavan.

I kakve to veze ima s fraktalima? Uzevši u obzir iterativnost (nisam siguran je li ovo uopće hrvatska riječ) postupka generiranja L-sistema lako se vidi da oni često rezultiraju strukturama koje slijede načelo samosličnosti. Samoslčnost je jedna od osnovnih opazivih karakteristika fraktala. Riječ je o činjenici da fraktal pri ma kako velikom povečanju/smanjenju zadržava oblik osnovne strukture koja ga je proizvela (tj. zadržava dimenziju, ali to je jedna druga priča). Zbog fraktalne prirode L-sistema, biološki sitemi postaju pravo područje za primjenu fraktalne geometrije. Ako se uzme u obzir i česta i lako opaziva pojava kaosa u tim sistemima, nije ni čudo da su se upravo prve naznake teorije kaosa pojavile u biologiji, ekologiji i meteorologiji, a tek kasnije u fizici. Biologija je kao i druge dvije znanosti dugo odolijevala prodoru matematike u svoje vode. Kad se jednom taj prodor desio, biolozi su raspolagali s modelima preuzetim iz fizike. Ubrzo se pokazalo da su takvi modeli nedostatni. Jedan za drugim davali su netočene i neupotrebljive rezultate. Problem je bio u temeljnom pristupu. Fizičar pokušava izolirati mali komadić pojave, dobro ga proučiti, dodati mu novi komadić i tako dalje sve dok ne dobije model upotrebljiv za dani slučaj. S ekološkim i meteorološkim sistemima to jednostavno ne ide. Oni zahtjevaju globalni pristup. Stoga su ove znanosti vrlo brzo postale otvorene novim i egzotičnim spoznajama teorije kaosa… O problemima modeliranja ću još pisati…

I mala zanimljivost…

Da dokažem kako fraktali imaju veze s L-sistemima zadat ću sljedeći sistem:

• aksiom: “F”
• pravilo prepisivanja: “F” -> “F+F–F+F”
• kut: 60 stupnjeva.

Ako ga sada renderiramo, dobivamo:

Što je dio (trećina) Kochove pahuljice

Reference

• Algorithmic Botany: Home
  
• An Introduction to Lindenmayer Systems
• Lindenmayer System – from Wolfram MathWorld