Úvod Teorie Studium CA Aplikace Souvislosti Buněčné automaty Radek Pelánek Úvod Teorie Studium CA Aplikace Souvislosti Souvislosti Kam směřujeme? modelování systémů „od spodu - individua, lokální interakce agent based modeling (ABM) – modelování založené na agentech proč buněčné automaty (cellular automata, CA)? předchůdce ABM: historicky i technicky jednoduché, snadno formalizovatelné a přitom silné několik zajímavých modelů Úvod Teorie Studium CA Aplikace Souvislosti Souvislosti Svět sedmikrásek modelování shora modelování zdola systémový model buněčný automat Úvod Teorie Studium CA Aplikace Souvislosti Souvislosti Základní principy diskrétní prostor i čas striktně lokální interakce mnoho „buněk simulace klíčová Úvod Teorie Studium CA Aplikace Souvislosti Souvislosti Hra Život čtverečkovaná síť buněk, sousedi se počítají i diagonálně stavy buněk: živá, mrtvá hraje se na kola pokud je buňka živá: < 2 sousedi ⇒ umírá na osamělost > 3 sousedi ⇒ umírá na přehuštění 2 ∨ 3 sousedi ⇒ přežívá pokud je buňka mrtvá: 3 sousedi ⇒ ožívá jinak zůstává mrtvá Úvod Teorie Studium CA Aplikace Souvislosti Souvislosti Hra Život: příklad Úvod Teorie Studium CA Aplikace Souvislosti Souvislosti Základní poselství Jednoduchá pravidla mohou vést ke složitému chování. Vztah k chaosu, komplexitě, vyčíslitelnosti. Úvod Teorie Studium CA Aplikace Souvislosti Souvislosti Historie – vybrané poznámky 40. a 50. léta: von Neuman, Ulam: základní formalismus (studium sebe-reprodukce) 1970: Conway: hra Život, článek v Scientific American (Gardner), značná pozornost 1983: Wolfram: přehledový článek o CA, začátek studia CA ve fyzice 2002: Wolfram: A New Kind of Science Úvod Teorie Studium CA Aplikace Souvislosti Definice Základní charakteristiky CA diskrétní prostor mřížka buněk homogenita všechny buňky identické diskrétní stavy každá buňka může mít jen konečný počet stavů lokální interakce stav buňky určen jen na základě blízkého okolí diskrétní dynamika stav se mění synchronizovaně, v diskrétních časových krocích Úvod Teorie Studium CA Aplikace Souvislosti Definice Mřížka jednorozměrná dvourozměrná: obdélníková, šestiúhelníková, ... vícerozměrná Úvod Teorie Studium CA Aplikace Souvislosti Definice Okolí buňky N(i) - okolí buňky i, příklady: Úvod Teorie Studium CA Aplikace Souvislosti Definice Okrajová podmínka teorie – nekonečné mřížky simulace – konečné mřížky periodická okrajová podmínka (kružnice, torus) fixní hodnota okrajových buněk Úvod Teorie Studium CA Aplikace Souvislosti Definice Lokální stavy konečná množina lokálních stavů: Σ = {0, . . . , k − 1} stav i-té buňky v čase t značíme σi (t) ∈ Σ Úvod Teorie Studium CA Aplikace Souvislosti Definice Přechodové pravidlo Pravidlo určuje následující stav na základě stavů buněk v okolí: φ : Σn → Σ, kde n je velikost okolí σi (t + 1) = φ(σj (t), j ∈ N(i)) Úvod Teorie Studium CA Aplikace Souvislosti Definice Speciální třídy CA Zpřísněním požadavků na přechodovou funkci dostáváme speciální třídy CA: legal zachování „klidového stavu + symetrie totalistic přechodová funkce pracuje pouze se součtem hodnot z okolí outer-totalistic rozhoduje stav buňky + součet z ostatních additive lineární funkce (modulo k) přes hodnoty z okolí Úvod Teorie Studium CA Aplikace Souvislosti Definice Sémantika: stavový prostor stav automatu: přiřazení lokálních stavů všem buňkám (M → Σ) deterministické: každý stav má právě jednoho následníka konečná mřížka → konečný stavový prostor → každý výpočet se časem zacyklí Úvod Teorie Studium CA Aplikace Souvislosti Jednorozměrné automaty Jednorozměrné CA k stavů, r velikost okolí pravidlo tvaru: σi (t + 1) = φ(σi−r (t), . . . , σi (t), . . . , σi+r (t)) Úvod Teorie Studium CA Aplikace Souvislosti Jednorozměrné automaty Zakreslení dynamiky G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Jednorozměrné automaty Příklad: pravidla G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Jednorozměrné automaty Příklad: dynamika G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Wolframova klasifikace Wolframova klasifikace Třída I Vývoj spěje vždy do fixního stavu, ve kterém se již stav buněk nemění. Třída II Vývoj spěje k jednoduchým periodickým strukturám, které se neustále opakují. Třída III Aperiodické, chaotické, náhodně vypadající chování. Třída IV Složité vzory, které se pohybují „prostorem . Úvod Teorie Studium CA Aplikace Souvislosti Wolframova klasifikace Třída I: ukázky G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Wolframova klasifikace Třída II: ukázky G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Wolframova klasifikace Třída III: ukázky G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Wolframova klasifikace Třída IV: ukázky G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Wolframova klasifikace Srovnání s programy (vyčíslitelnost) Třída I (fixní stav) triviální programy (bez cyklů či omezený počet opakování) Třída II (jednoduché cyklení) programy, které se triviálně zacyklí Třída III (chaos) generátor náhodných čísel Třída IV (komplexní vzory) programy, které dělají zajímavé věci Úvod Teorie Studium CA Aplikace Souvislosti Langtonův parametr Langtonův parametr jeden ze stavů označíme za „klidový stav q N - celkový počet pravidel pro jednorozměrný automat s k lokálními stavy a okolím velikosti r je N = k2r+1 nq - počet pravidel, která vedou do klidového stavu q Langtonův lambda parametr: λ = N − nq N Úvod Teorie Studium CA Aplikace Souvislosti Langtonův parametr Langtonův parametr a Wolframovy třídy G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Langtonův parametr Poznámky připomenutí základního poselství: Jednoduchá pravidla mohou generovat složitá chování. model může inspirovat k zajímavým úvahám i bez toho, aby modeloval něco zcela konkrétního Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Hra Život čtverečkovaná síť buněk, sousedi se počítají i diagonálně stavy buněk: živá, mrtvá hraje se na kola pokud je buňka živá: < 2 sousedi ⇒ umírá na osamělost > 3 sousedi ⇒ umírá na přehuštění 2 ∨ 3 sousedi ⇒ přežívá pokud je buňka mrtvá: 3 sousedi ⇒ ožívá jinak zůstává mrtvá Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Cíle návrhu pravidel Autor Conwey, inspirován von Neumannem, výzkumem sebe-reprodukce. Cíl: jednoduché pravidlo s náročnou předpověditelností. Pro žádnou počáteční konečnou konfiguraci by nemělo být triviálně dokazatelné, že roste nade všechny meze. Měly by existovat počáteční konfigurace, které (alespoň zdánlivě) rostou nade všechny meze. Měly by existovat počáteční konfigurace, které se vyvíjejí a mění dlouhou dobu než upadnou do stabilního stavu (resp. krátkého oscilujícího cyklu). Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Nekonečný růst Conwayova hypotéza: „nekonečný růst ve hře Život není možný nabídl $50 tomu, kdo to dokáže nebo vyvrátí hypotéza neplatí dokázáno během 1 roku tým z MIT nalezli konfiguraci vedoucí k „nekonečnému růstu Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Proč „Život ? Je pravděpodobné, že pokud poskytneme dostatečný prostor a začneme v náhodném stavu, tak po dostatečně dlouhé době osídlí části prostoru inteligentní sebe-reprodukující bytosti. (J. H. Conway) Hra má schopnost z náhodného stavu vytvářet pravidelné a zajímavé struktury (srovnej primordial soup). Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Stabilní konfigurace G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Periodické konfigurace G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Pohybující se konfigurace G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Hra Život G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Další ... YouTube: „game of life , např. https://www.youtube.com/watch?v=C2vgICfQawE https://www.youtube.com/watch?v=R9Plq-D1gEk http://www.conwaylife.com/ http://www.conwaylife.com/wiki/Main_Page Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Garden of Eden Konfigurace, která nemá předchůdce. Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Turingovská síla CA pro každý TS existuje CA, který zadaný TS simuluje (jednoduché) pro každý TS a slovo w existuje konečná počáteční konfigurace hry Život, která simuluje výpočet TS nad tímto slovem platí dokonce i pro jednorozměrné pravidlo R110 (2 hodnoty, okolí velikosti 1) Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Simulace Turingova stroje pomocí hry Život data = gliders (kluzáci) důležité prvky: anihilace (srážka dvou kluzáků), eater (požírač kluzáků) data stream = glider gun logické funkce – viz obrázek paměť – registry (viz Minského stroj) Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Simulace logických funkcí G. Flake, The Computational Beauty of Nature Úvod Teorie Studium CA Aplikace Souvislosti Hra Život Základní poselství: připomenutí Jednoduchá pravidla mohou vést ke složitému chování. Úvod Teorie Studium CA Aplikace Souvislosti Další příklady Další jednoduché 2D CA parity totalistic 2D automaty majority model viz NetLogo demo Úvod Teorie Studium CA Aplikace Souvislosti Sebe-reprodukce a emergence Sebe-reprodukce Počáteční impuls pro studium CA, von Neuman: pozorování: reprodukce v přírodě: udržení (zvyšování) složitosti stroje: snižování složitosti kritéria návrhu: univerzální stroj: dokáže dle popisu sestrojit cokoliv sebe-reprodukce: dokáže vyrobit vlastní kopii sestrojil takový automat, 29 lokálních stavů, velmi komplikovaný Úvod Teorie Studium CA Aplikace Souvislosti Sebe-reprodukce a emergence Langtonův automat Langton: volnější definice sebe-reprodukce: studuje, co je pro sebe-reprodukci „nutné (nikoliv „dostatečné ) kritéria návrhu: řízení reprodukce nemá být pasivní - řízeno nejen mechanismem (pravidly) aktivní role struktury, která se sebe-reprodukuje Úvod Teorie Studium CA Aplikace Souvislosti Sebe-reprodukce a emergence Úvod Teorie Studium CA Aplikace Souvislosti Sebe-reprodukce a emergence Úvod Teorie Studium CA Aplikace Souvislosti Sebe-reprodukce a emergence Úvod Teorie Studium CA Aplikace Souvislosti Sebe-reprodukce a emergence Emergence „vynořující se chování příklad: 4D mřížka, lokálně chování náhodné, graf znázorňuje počty aktivovaných buněk ve dvou po sobě jdoucích iteracích (→ struktura) tématem se budeme zabývat u ABM Úvod Teorie Studium CA Aplikace Souvislosti Rozšíření Rozšíření CA pravděpodobnostní pravidla nejsou deterministická, ale pravděpodobnostní nehomogenní uvolnění požadavku na identitu buněk strukturně dynamické mění se nejen hodnota buněk, ale i vlastní mřížka (tj. okolí jednotlivých buněk) spojité např. hodnoty z intervalu [0, 1] Úvod Teorie Studium CA Aplikace Souvislosti Rozšíření Deterministické vs pravděpodobnostní Úvod Teorie Studium CA Aplikace Souvislosti Základní oblasti aplikace CA modelování a simulace: dynamické systémy (např. proudění vody), formace vzorů, ... výpočetní mechanismus (hardwarová implementace) fundamentální modely fyziky (vesmír na principu CA) Úvod Teorie Studium CA Aplikace Souvislosti Formace vzorů Vzory v přírodě Úvod Teorie Studium CA Aplikace Souvislosti Formace vzorů Vznik vzorů jako CA Úvod Teorie Studium CA Aplikace Souvislosti Formace vzorů Model Úvod Teorie Studium CA Aplikace Souvislosti Formace vzorů Model – princip Úvod Teorie Studium CA Aplikace Souvislosti Růst a rozpad organismů Rozpad kostí Úvod Teorie Studium CA Aplikace Souvislosti Vědy o Zemi Eroze Rozšíření: voda v krajině – ilustrace vlivu stromů na koloběh vody Úvod Teorie Studium CA Aplikace Souvislosti Vědy o Zemi Požár šíření požáru v lese ilustrace fázového přechodu rozšíření: požáry a hašení – ilustrace dopadu hašení na velikost požáru Úvod Teorie Studium CA Aplikace Souvislosti Chemie Chemie NetLogo demo – Chemistry Boiling Crystalization Belousov-Zhabotinsky reaction http://www.youtube.com/watch?v=GEF_NtTNeMc&NR=1 Waves Úvod Teorie Studium CA Aplikace Souvislosti Sociální systémy Sociální systémy NetLogo demo: Social Science Voting – majority rule jednoduchý základní model, který se dále rozšiřuje (např. sociální sítě) spojitost Ising model, magnetismus Úvod Teorie Studium CA Aplikace Souvislosti Souvislosti ABM agent based modeling – viz příští přednáška modelování biologických procesů růst, formace vzorů, ... vyčíslitelnost nepředvídatelnost, univerzalita, ... chaos sensitivita k počátečním podmínkám, bifurkace, přechod od řádu k chaosu, ... fyzika nový pohled na základní principy fyziky Úvod Teorie Studium CA Aplikace Souvislosti Nový pohled na fyziku vesmír jako CA? (diskrétní čas i prostor) paralela s „objevováním dynamiky R110 při pohledu zvenčí můžeme vidět spoustu zajímavých jevů: pohybující se „částice a jejich kolize, ... přitom základní mechanismus je triviální viz též http://xkcd.com/505/ Úvod Teorie Studium CA Aplikace Souvislosti Shrnutí jednoduchá pravidla, lokální interakce studujeme systémy „od spodu Jednoduchá pravidla mohou vést ke složitému chování.