Köszi az információkat! Nagyon érdekes mind a kvantum, mind a Turning analógia. Van már valamiféle gyakorlati eredmény is? Arról tudnál még némi infót adni, hogy nem reguláris rácsokon mennyire értelmes sejtautomatákkal foglalkozni? Interneten elég kevés hivatkozást találtam pl. a Penrose-alapú autómatákról. Általánosabb gráfokon foglalkoztak már automatákkal? Pl. Boole-hálón stb.
Diszkrét modell. A konfigurációs tér (0,1) értékü föggvények
az egész számokon (mondjuk). Shiftnek hivják azokat
a részhalmazokat, amelyek zártak a pontonkénti konvergenciára és invariánsak az eltolásokra.
Egy sejtautomata mit csinál, egy konfigurációhoz konfigurációt rendel.
Namost egy ilyen shiftnek van egy mérőszáma, amit
entrópiának neveznek, de az pontosan az amit divatosabban
fraktáldimenziónak neveznek. Ha van egy sejtautomatád
ami nem képez két állapotot ugyanabba, az megtartja
a dimenziót.
............................................
Kvantummodell. A konfigurációs tér a valós számértékü négyzetesen szummálható függvények tere az egészeken.
Ezek egy Hilbert teret alkotnak, amin ugyanugy van eltolas
mint a diszkret esetben. Itt is van shift, ezeket Neumann
János invariáns altereknek nevezte. Ezek zárt, lineáris alterek amelyek zártak az eltolásokra. Ezeknek is
van valamiféle dimenziójuk, ami tehát az entrópia (vagy fraktáldimenzió kvantumanalogonja). Alapvetően
úgy kell kiszámolni, hogy veszed az invariáns alteret, ami
egy zárt altér a Hilbert térben és erre veszed a merőleges
vetitést. Ennek van egy mátrixa. Az eltolás invariancia
miatt a diagonálisban ugyanazok a számok szerepelnek.
Na ez a szám a dimenzió. itt si beszélhetünk transzformációkról
és az hasonló feltételek mellett, megtartja a dimenziót.
Ez ugyanúgy akármilyen szám lehet mint a fraktáldimenzió.
Fourier transzformációval lehet konstruálni érdekes
példákat. Itt persze lineáris alterekről van szó.
A diszkrét esetben is lehet ilyesmit csinálni, csak
érdekes dolog nem tud kijönni. (khmm, egész számokra,
aztán, hogy kijöhet-e valami érdekes általában, az praktikusan az Atiyah sejtés, kb. a legérdekesebb matematikai
probléma a világon)
.................
Ezt a trükköt a projekcióval mindig meg lehet csinálni,
akármilyen rácson. De a diszkrét esetben általában
nem tudnak értelmes dolgot csinálni. Azaz, bizonyos
csoportokra tudnak, és nem tudják, hogy az a bizonyos
csoportosztály esetleg az összes csoporté vagy sem.
A Szindbad76 által belinkelt cikkben van szó a Garden of Eden problémáról. Azt entrópiákkal elég könnyen meg lehet csinálni (68-ban oldották meg). Az a bizonyos Ceccherini
cikk éppen erről szól.
Konkret kapcsolat van a sejtautomatak es a kvantuumelmelet
kozott.
..............
Vegyunk egy automatat. Mondjuk legyen ket allapot benne
0 es 1. Az allapotter tehat a kovetkezo:
A sikracs minden egyes pontjahoz hozzarendelunk 0-t vagy 1-et, ez ad egy konfiguraciot. A konfiguracios teren felvesszuk a klasszikus szorzatmetrikat. (pontonkenti konvergencia topologiaja)
Vegyunk egy folytonos transzformaciot a konfiguracios
teren, ami felcserelheto a sikracs eltolasaival.
Allitas: Ha nincs ket konfiguracio amit ugyanabba visz
egy ilyen transzformacio, akkor minden konfiguracio
elo all a transzformacio kepekent.
Ez 1973 ota ismert, akarhany dimenzioban, nemcsak
a sikban (Gottschalk es Hedlund).
A mai napig megoldatlan a kovetkezo kerdes:
Mi a helyzet, ha egy tetszoleges csoportot veszunk.
Gromov (1999) bebizonyitotta, hogy ha a csoport nem
nagyon ronda (rezidualisan amenabilis) akkor a Gottschalk
Hedlund tetel igaz marad.
Az oka a dolognak az, hogy ezeken a csoportokon van
egy un. mean dimension ami rendelkezik bizonyos
szep tulajdonsagokkal. Entropia nincs, az csak igazi amenabilisen van, de valami van helyette, ezeken a csoportokon.
A kvantuum analogia viszont MINDEN csoportra mukodik,
na ez a meglepo. Ott ugyanis az invarians altereken
van egy dimenzio, a von Neumann dimenzio. Az a kerdes,
hogy van e minden sejtautomatara valamifele von Neumann dimenzio szeru valami.
Irodalom: (szerintem erdekes es olvashato) Ceccherini-Machi-Scarabotti: Amenable groups and cellular automata. Ann.Inst.Fourier 49 (1999) 673-685
A téma őskori, már Neumann is foglalkozott vele.
Magyaroszágon a 70-es évek végén vett új lendületet. Többen kísérleteztek mikroprocesszorok sejttérbe rendezésével. Kapásból csak Legendi Tamás neve jut eszembe.
Jelent meg könyv is, címe: Sejtautomata algoritmusok. Kerítsd elő, megéri.
A sejtautomata cellak strukturaba rendezett halmaza amely egy diszkret dinamikai rendszert közelit. Azaz ter, idö, es a felvehetö allapotok diszkretek. A terdiszkretizalast legegyszerubben egy szabalyos halozattal lehet elkepzelni. A szabalyos halozat elemei a cellak. A cella allapotokat vehetnek fel, amelyek veges szamuak lehetnek. A cellak allpota egyszerre valtozhat meg egy lokalis, a szomszedok között ertelmezett ugynevezett allapotatmenetfüggveny szerint. Igy a cella allapota csak az atmenetfüggvenytöl es a sajat elözö allapotatol függ. A lenyeg, hogy a cellak allapota egyszerre, orajelre valtozhat meg, amely az adott problema numerikus szinten valo nagymerteku parhuzamositasat teszi lehetöve.
A sejtautomata müködese az allapotatmentfüggveny parhuzamosan, több peldanyban valo kiszamitasat jelenti. A fizikai alkalmazasok lenyege, hogy nem szükseges a porblemat leiro egyenletet (pl. Maxwell egyenleteket) felirni, hanem a cellak között ertelmezett atmenetfüggvenyek (amelyek igen egyszerüek is lehetnek) alkalmazasaval a feladat közelithetö. Ez ott lehet igen elönyös
ahol pl a fizikai egyenlet, hagyomanyos numerikus technikaval (pl. vegeselem modszer) nehezen oldhato meg, a fellepo nemlinearitasok
miatt. Az ilyen sejtautomatakat pl. a repülögepiparban racsgazoknak nevezik.
Legtöbbet idezett irodalom Tommaso Toffoli and Norman Margolus. Cellular Automata Machines. MIT Press, London, 1987.
De az altavistan ezer forraskodot talalsz. Szerintem van mar ilyen MatLab konyvtar is. Mathematica egesz biztos van, mert S.Wolfram aktivan resztvett a sejtautomata kifejleszteseben.
Van egy régi Codd-Icra 8 bites sejtszimulációm, még XT-re írtam egy barátommal, ha van kedved átírni windowsra, szívesen elküldöm, C-ben van írva és direkt videó címzést használ EGA-ra. Jó lenne látni, hogy egy mai teljesítményű gépen mit alakít a program, elég szép sejttereket tenyésztettünk vele annak idején, de megvan az eredeti állapottér is persze.
Ha barkinek "lovese" van ehhez a temahoz, vagy tud olyan linkeket, ahol errol tobbet tudhatok meg, netan letoltheto forraskodok vagy programok vannak, kerem irjon ide egy sort.
