{"id":2174,"date":"2009-01-31T22:15:16","date_gmt":"2009-01-31T21:15:16","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=2174"},"modified":"2023-05-24T16:07:16","modified_gmt":"2023-05-24T14:07:16","slug":"life-der-zellautomat","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2009\/01\/life-der-zellautomat.htm","title":{"rendered":"Life (der Zellautomat)"},"content":{"rendered":"<div style='text-align:right;'><small>(<a href='https:\/\/www.herr-rau.de\/wordpress\/2009\/01\/life-der-zellautomat.htm#comments'>2 Kommentare.<\/a>)<\/small> <\/div>\n<p>Es gibt eine Art Computerspiel namens <em>Life<\/em>, nach dem Erfinder auch <em>Conway&#8217;s Game of Life<\/em> genannt. Man spielt nicht selber mit, sondern man setzt ein paar Zellen in eine leere Welt und schaut zu, wie sie sich vermehren oder sterben. Das sieht zum Beispiel so aus:<\/p>\n\n\n\n<figure class=\"wp-block-video\"><video height=\"120\" style=\"aspect-ratio: 160 \/ 120;\" width=\"160\" controls src=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life.mp4\"><\/video><\/figure>\n\n\n\n<p>Die Regeln f\u00fcr das \u00dcberleben, Fortpflanzen und Sterben lauten so:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Fortplanzung: Hat eine unbesetzte Zelle genau drei lebende Nachbarn (in den acht umgebenden Feldern), dann entsteht in der n\u00e4chsten Generation dort eine neue lebende Zelle.<\/li>\n\n\n\n<li>Leben oder Tod: Eine lebende Zelle mit genau 2 oder 3 Nachbarn \u00fcberlebt in die n\u00e4chste Generation. Bei mehr oder weniger Nachbarn stirbt sie.<\/li>\n<\/ul>\n\n\n\n<p>Wenn man das ein paar Mal mit verschiedenen Ausgangskonstellationen spielt, stellt man einige Sachen fest. Es gibt zum Beispiel manche Kombinationen aus Zellen, die stabil sind: der Brotkorb oder die Bienenwabe etwa. Wenn die nicht gest\u00f6rt werden, dann stirbt keine Zelle und keine neue entsteht.<\/p>\n\n\n\n<p><img decoding=\"async\" src=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_stable.gif\"><br><small>(Arbol1, CC-BY-SA, <a href=\"http:\/\/de.wikipedia.org\/w\/index.php?title=Datei:2g3_stabile.GIF&amp;filetimestamp=20040505103734\">Quelle<\/a>)<\/small><\/p>\n\n\n\n<p>Dann gibt es noch Kombinationen, die oszillierend stabil sind. Am einfachsten ist der Blinker, der periodisch zwischen zwei verschiedenen Formen wechselt.<\/p>\n\n\n\n<p><img decoding=\"async\" src=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_blinker.gif\"><br><small>(Arbol1, CC-BY-SA, <a href=\"http:\/\/de.wikipedia.org\/w\/index.php?title=Datei:2g3_o01.gif&amp;filetimestamp=20040502105220\">Quelle<\/a>)<\/small><\/p>\n\n\n\n<p>Und dann gibt es noch die Gleiter. Die sehen so aus, als bewegen sie sich fort, und zwar diagonal. Immer nach vier Takten haben sie sich horizontal und vertikal eine Zelle weiterbewegt.<\/p>\n\n\n\n<p><img decoding=\"async\" src=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_glider.gif\"><br><small>(<a href=\"http:\/\/en.wikipedia.org\/wiki\/File:Game_of_life_animated_glider.gif\">Quelle<\/a>)<\/small><\/p>\n\n\n\n<p>Insgesamt stellt man bei den ersten Versuchen fest, dass fr\u00fcher oder sp\u00e4ter die Welt zur Ruhe kommt und nur noch aus stabilen Figuren besteht und vielleicht einigen Gleitern dazu, die immer weiter in die Unendlichkeit hinausfliegen: Die Gesamtpopulation w\u00e4chst nicht mehr.<\/p>\n\n\n\n<p>Bald nachdem Conway das kleine Spielchen erfand, stellte er eine Herausforderung: Kann es eine Startpopulation von Zellen geben, die immer gr\u00f6\u00dfer wird? F\u00fcnzig Dollar schrieb er aus und rechnete laut Wikipedia nicht damit, sie zahlen zu m\u00fcssen.<\/p>\n\n\n\n<p>Bis dieses Ding erfunden w\u00fcrde: eine Gleiterkanone.<\/p>\n\n\n\n<p><img decoding=\"async\" src=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_Gospers_glider_gun_1.png\"><br><small>(<a href=\"http:\/\/en.wikipedia.org\/wiki\/File:Game_of_life_glider_gun.png\">Quelle<\/a>)<\/small><\/p>\n\n\n\n<p>So sieht sie in Betrieb aus:<\/p>\n\n\n\n<p><img decoding=\"async\" src=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_Gospers_glider_gun_2.gif\"><br><small>(Kieff, CC-BY-SA, <a href=\"http:\/\/en.wikipedia.org\/wiki\/File:Gospers_glider_gun.gif\">Quelle<\/a>)<\/small><\/p>\n\n\n\n<p>Periodisch entsteht ein neuer Gleiter, und damit war gezeigt, dass die Gesamtpopulation bei Life immer weiter ansteigen kann.<\/p>\n\n\n\n<p>Das war aber nur der Anfang. Weitere Gleiterkanonen wurden entdeckt. Bald kamen die Raumschiffe dazu: LWSS, MWSS, HWSS (lightweight\/middleweight\/heavyweight spaceship) und kompliziertere Varianten.<br>Nach und nach entstanden immer umfangreichere Populationen. Es gibt &#8222;Puffer&#8220;, das sind Konvois von Zellen, die sich zum Beispiel nach rechts bewegen und dabei einen Strom von M\u00fcll hinterlassen &#8211; M\u00fcll, der sich nach kurzer Zeit zu Gleiterkanonen entwickeln kann, die dann das tun, was sie am besten k\u00f6nnen &#8211; Gleiter produzieren. Es gibt &#8222;Filler&#8220;, die versuchen, die Welt mit so vielen Zellen und so rasch wie m\u00f6glich zu f\u00fcllen. Man geht davon aus, dass die maximale Zellendichte 50% betr\u00e4gt.<\/p>\n\n\n\n<p>Und dann wurde es noch komplizierter. Primzahlberechnung: Eine Population, die einen Strom von Gleitern erzeugt, und nur jeden x-ten Gleiter durch ein Tor passieren l\u00e4sst &#8211; und zwar dann, wenn x eine Primzahl ist. Nachbildungen verschiedener elektrischer Schaltkreise, mit einem kontinuierlichen Strahl von Gleitern als informationstragendem Stromfluss. Und wenn man Schaltkreise hat, dann kann man auch einen Computer nachbauen, wenn man denn wollte. Ja, mit Life kann man alles berechnen, was man berechnen kann. Die folgende Population berechnet Fermat-Primzahlen:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><a href=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_fermat_prim.png\"><img loading=\"lazy\" decoding=\"async\" width=\"550\" height=\"500\" src=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_fermat_prim.png\" alt=\"life_fermat_prim\" class=\"wp-image-2219\" title=\"life_fermat_prim\" srcset=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_fermat_prim.png 550w, https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_fermat_prim-150x136.png 150w\" sizes=\"auto, (max-width: 550px) 100vw, 550px\" \/><\/a><\/figure>\n\n\n\n<p>Eine Fermat-Zahl hat die Form F<sub>n<\/sub> = 2<sup>(2<sup>n<\/sup>)<\/sup> + 1, wobei n eine nat\u00fcrliche Zahl ist. F\u00fcr n = 1 bis 5 sind die entstandenen Zahlen Primzahlen, <em>vermutlich<\/em> gibt es keine weitere Fermat-Zahl, die prim ist. Die Life-Konfiguration oben wird rechnen und rechnen, und wenn noch eine Fermat-Zahl herauskommt, wird sie sich aufl\u00f6sen.<\/p>\n\n\n\n<p><strong>Vom Berechnen:<\/strong><\/p>\n\n\n\n<p>Stellen wir uns diese zugegebenerma\u00dfen arg unwahrscheinliche Situation vor: Ein Lehrer gibt seinen Sch\u00fclern den Auftrag, jeweils ein eigenes Life-Muster zu erzeugen, f\u00fcr ein Poster vielleicht. Er m\u00f6chte, dass jeder ein eigenes entwirft, und nicht einfach das von einem Mitsch\u00fcler nimmt und lediglich ein paar Generationen weiterlaufen l\u00e4sst. Weil der Lehrer viele Sch\u00fcler hat, h\u00e4tte er gerne ein Computerprogramm, in das man zwei <em>beliebige<\/em> verschiedene Momentaufnahmen einer Life-Welt eingibt, und das Programm rechnet aus, ob es m\u00f6glich ist, dass sich die eine Situation aus der anderen entwickeln kann oder nicht. Wenn das Programm ausspuckt: Jawoll, dieser eine Zustand kann sich nicht aus dem anderen entwickeln, die sind grundverschieden, dann wei\u00df der Lehrer, dass hier zumindest kein einfaches Abschreiben stattgefunden hat.<\/p>\n\n\n\n<p>Nur ist es leider unm\u00f6glich, so ein Programm zu schreiben. Braucht man gar nicht erst versuchen. Wird nicht gehen. Nie nicht. Das ist so quasi das Perpetuum Mobile der Informatik: Kann nicht sein.<\/p>\n\n\n\n<p>Denn das Problem ist <em>unentscheidbar<\/em>. Das ist ein Fachbegriff aus der theoretischen Informatik, den ich bei den formalen Sprachen immer mal wieder erw\u00e4hnt habe. Die genaue Erkl\u00e4rung muss warten, bis ich meinen Eintrag zu Chomsky 0 schreibe, der Menge der Sprachen, die immerhin semi-entscheidbar sind. Grunds\u00e4tzlich kann man kein Programm schreiben, das \u00fcberpr\u00fcft, ob zwei andere Programme sich unter allen Umst\u00e4nden und f\u00fcr alle Eingabewerte immer gleich verhalten werden. Ein &#8222;Programm&#8220; ist dabei alles, was so viel berechnen kann wie eine Turingmaschine, oder eine simple Programmiersprache, die einigen wenigen Kriterien gen\u00fcgt. (Oder was man mit dem Lambda-Kalk\u00fcl beschreiben kann. Aber da begebe ich mich endg\u00fcltig auf halbverstandenes Terrain.)<\/p>\n\n\n\n<p>Und ja, jemand hat auch eine Turing-Maschine mit Life produziert:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><a href=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_tm.png\"><img loading=\"lazy\" decoding=\"async\" width=\"498\" height=\"486\" src=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_tm.png\" alt=\"life_tm\" class=\"wp-image-2220\" title=\"life_tm\" srcset=\"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_tm.png 498w, https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_tm-150x146.png 150w\" sizes=\"auto, (max-width: 498px) 100vw, 498px\" \/><\/a><\/figure>\n\n\n\n<p>Fu\u00dfnote: Genau genommen ist Life ein Beispiel f\u00fcr einen Zellautomaten. Die bestehen aus vielen benachbarten Zellen (im diesem Fall in einer Schachbrettwelt, es k\u00f6nnte aber auch eine Welt aus Sechseckfeldern oder eine dreidimensionale sein), die bestimmte Zust\u00e4nde annehmen k\u00f6nnen (in diesem Fall nur zwei, lebendig oder unbelebt, es k\u00f6nnten aber auch mehr sein) und die nach bestimmten Regeln ihre Zust\u00e4nde \u00e4ndern.<\/p>\n\n\n\n<p><strong>Links:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a href=\"http:\/\/golly.sourceforge.net\/ \">Golly<\/a> (sch\u00f6ne Life-Implementierung f\u00fcr verschiedene Plattformen; mitgeliefert vieleviele Beispiele)<\/li>\n\n\n\n<li><a href=\"http:\/\/de.wikipedia.org\/wiki\/Conways_Spiel_des_Lebens \">Wikipedia-Eintrag<\/a> (deutsch) und <a href=\"http:\/\/en.wikipedia.org\/wiki\/Conway%27s_Game_of_Life \">Wikipedia-Eintrag<\/a> (englisch) &#8211; beide sind lesenswert<\/li>\n\n\n\n<li><a href=\"http:\/\/en.wikipedia.org\/wiki\/Life-like_cellular_automaton \">andere Vermehrungs-\/Todes-Regeln f\u00fcr die Life-Welt<\/a> und was dabei passieren kann (Wikipedia)<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>(2 Kommentare.) Es gibt eine Art Computerspiel namens Life, nach dem Erfinder auch Conway&#8217;s Game of Life genannt. Man spielt nicht selber mit, sondern man setzt ein paar Zellen in eine leere Welt und schaut zu, wie sie sich vermehren oder sterben. Das sieht zum Beispiel so aus: Die Regeln f\u00fcr das \u00dcberleben, Fortpflanzen und [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":2219,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[25],"tags":[227,86],"class_list":["post-2174","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-informatik","tag-informatik","tag-wissenschaftliches"],"jetpack_featured_media_url":"https:\/\/www.herr-rau.de\/wordpress\/archiv\/life_fermat_prim.png","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/2174","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/comments?post=2174"}],"version-history":[{"count":3,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/2174\/revisions"}],"predecessor-version":[{"id":57974,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/posts\/2174\/revisions\/57974"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media\/2219"}],"wp:attachment":[{"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/media?parent=2174"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/categories?post=2174"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.herr-rau.de\/wordpress\/wp-json\/wp\/v2\/tags?post=2174"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}