Rekursionstheorie - "Gödel Escher Bach"

(Stephan König) 
 
 
   
1: Über Autor und Buch

1.1: Douglas R. Hofstadter

  • geboren 1945 in New York
  • studiert Physik
  • 1975 Promotion
  • Gastprofessuren unter anderem in:
  • lehrt Kognitionswissenschaft an der Indiana University
  • weitere Bücher:
  • 1.2: Gödel Escher Bach

    1.2.1: Gödel

    Mathematiker und Logiker aus Österreich. Geboren am 28.4. 1906 in Brün, gestorben am 14.1.1978 in Princeston. Studiert Mathematik und Physik in Wien, unterichtet auch dort. Geht 1938 nach Princeston und wird dort 1953 zum Professor ernannt.
    Gödel gilt als einer der bedeutensten Logiker des 20.Jahrhunderts. 1930 bewies er die Vollständigkeit der Prädikatenlogig 1.Stufe. 1931 veröffentlichte Gödel seine beiden Unvollständigkeitssätze. 1938 zeigte er, daß Kontiniumshypothese und Auswahlaxiom nicht durch die restlichen Axiome der Mengenlehre widerlegt werden können. Gödel äußerte sich auch zu philosophischen Grundfragen der Mathematik, in der er einen dezidiert platonistischen Standpunkt vertrat. Ein weiteres Arbeitsgebiets Gödels waren die Grundlagen der Relativitätstheorie.

    1.2.2: Escher

    Mauritits Cornelius Escher wurde am 17.6.1898 in Leeutwarden geboren und starb am 27.3.1972 in Hilversum.Escher experimentierte in seiner Grafik mit Formen und ihren Metamorphosen mit dem Ziel spielerischer Verwirrung der Sinne. vexierbildhaft gebraucht er die Perspektive und kombiniert Gegensätze wie Tag und Nacht, innen und außen so, daß die Absurdität der Anordnung erst nach genauerer Betrachtung auffällt.

    1.2.3: Bach:

  •  geboren 1685 in Eisenach.
  • gestorben 28.7.1750 in Leipzig
  • Organist in Thüringen
  • 1717 Hohkapelmeister in Köthen.
  • 1723 Universitätsmusikdirektor in Leipzig.
  • Spätes Mittelalter und Barock werden in seinem Werk zusammengefaßt und gekrönt. Formen geistlicher, höflicher und weltlicher Musik durchdringen sich, teilweise in Verbindung mit lehrhaften Absichten. Seit der Wiederentdeckung durch Mendelson sieht man in Bach einen der größten Komponisten. Er schrieb über 200 Kirchenkantaten, Johannes- und Matthäuspassion, Weihnachtsoratorium, h-Moll-Messe, weltliche Kantaten, 6 brandenburgische Konzerte, Suiten, Orgel- und Klaviermusik. Spätwerk: Das musikalische Opfer, Kunst der Fuge.
     
    <Inhalt>
    1.3: Struktur des Buches:

    1.3.1: Hofstaedters Hauptthemen(unsortiert)

    Mathematische Logig, Philosophie der Mathematik, Artifizielle Intiligenz, Mögliche Welten Genetik, Übersetzung und Entschlüsselung / Bedeutung von Botschaften, Selbstbezug, Zen-Buddhismus, Chaostheorie, Gehirn und Denken, Programiersprachen, einzelne Teilgebiete der Mathematik, Musik, Kunst, verschiedene Bereiche der Biologie, Paradoxien, Bewußtsein und freier Wille.

    1.3.2: Zenon:

    geboren ungefähr 490 vor Christus in Elea. Circa v.C ist er auch dort gestorben. Elea liegt im heutigen Süditalien. Zenon war ein Schüler und Freund von Parmenides. Er stellte vier Paradoxien auf, die die Grundlage mathematischer Begrifflichkeit bildeten. Insbesondere der Begriff Unendlichkeit wäre ohne Zenon nicht so umfangreich bearbeitet wurden. Mit seinen Paradoxien will er die Unmöglichkeit von Bewegung und Veränderung beweisen.

    1.3.3: Archill und die Schildkröte

    Achill, der schnelle Gott der griechischen Antike läuft ein Wettrennen gegen eine irdische Schildkröte. Um das Rennen fair zu gestalten, gewährt Archill der Schildkröte einen Vorsprung. Anschaulich ist völlig klar, daß Archill die Schildkröte irgentwann einholt, doch genau dieses bestreitet Zenon. In seinem Paradoxon, schafft es Archill niemals die Schildkröte zu überholen. Zenons Argumentation lautet einfach: Angenommen, der Vorsprung der Schildkröte beträgt am Start 10 meter und die Archill ist zehnmal so schnell wie die Schildkröte. Wenn Archill die 10 meter aufgeholt hat, ist die Schildkröte einen meter weitergekommen. Hat Archill diesen geschafft, hat sich die Distanz auf 100 cm veringert, In der Zeit die Archill benötigt, den Vorsprung einzuholen, kommt die Schildkröte eine wenn auch noch so kleine Stecke vorwärts.

    Mathematisch stellt sich das Problem so dar:
    Achill läuft folgene Strecke: 10 meter, 1 meter, 0.1meter, 0.01 meter ... ,oder als Formel ausgedrückt:
     
       °°
    _____
    \
    /____   10 1-:
     i = 0
     

    Dies ist aber gerade die Formel für eine unendliche Reihe, die gegen 100/9 konvergiert, d.h nach gut 11 metern hat Archill die Schildkröte überholt. Aber gerade für die Begriffsbildung und Definition der unendlich geometrische Reihe war die Existenz von Zenons Paradoxon bedeutsam.Philosophen sehen in Zenons Paradoxon auch den indirekten Beweis daß Raum und Zeit nicht unendlich oft teilbar sind. Irgentwann keinen nahezu unendlich kleinen Schritt machen.Die beiden Protagonisten dieses Paradoxons hat Hofstaedter zu den Hauptfiguren seines Buches gemacht. Die Theorieen die Hofstadter in seinem Buch aufstellt, werden vorher durch einen Dialog angerissen. Aus diesen Dialogen entstannt dann später sogar ein Theaterstück.


    <Inhalt>

    2: Inhaltsangabe: Kleines harmonischen Labyrinth. (Dieser Dialog ist der Vordialog zum Kapitel Rekursion)

    Herr Schildkröte und Archill sind auf éinem Jahrmarkt. Herr S. ist besonders gut drauf, da eine Wahrsagerin einem Glücksfall geweissagt hast. Als beide sich auf dem höchsten Punkt des Riesenrades befinden, fliegt ein Hubschrauber auf sie zu. Sie werden eingeladen an Bord zu kommen. Das hätten sie besser nicht getan, denn sie werden von dem Magier Hexachlorophen J. Glücksfall entführt, der kein Hehl darausmacht Herrn S. verspeisen zu wollen. Sie werden ins Arbeitszimmer gesperrt. Dort entdecken sie ein Buch: "Aufregende Abenteuer des Archill und Herrn Schildkröte an verschiedenen Stellen der Welt". Die beiden beginnen zu lesen ...

    Herr S. ist bei Archill zu Hause und beschauen dessen Eschersammlung. Dort schauen sie sich das Bild "konkav und konvex" an. Herr S traut Archill ein Geheimnis an, er hat einen Pushsaft erfunden, der es ihm ermöglicht in zweidimensionale Welten zu gelangen. Sie trinken den Pushsaft und gelangen in das Bild "konkav und konvex". Dort befreit Archill einen Geist aus einer Wunderlampe und erhällt einen Wunsch. Er wünscht sich einen Metawunsch(Metawünsche sind Wünsche über Wünsche). Der Geist erklärt ihm, daß er Metawünsche nicht erfüllen könnte, doch über eine Kette von immer kleiner werdenen Geistern wird Archills Wunsch dennoch gewährt. Leider wünscht sich Archill, daß sein Wunsch nicht in Erfüllung geht. Das führt zum Disaster und die beiden nach Trumbolia versetzt und anschließend in ein weiteres Bild von Escher "Reptilien". Nun wollen sie wieder nach Hause. Um das Gegenmittel zum Pushsaft, den Poptonic zu bekommen folgen sie dem Bild und geraten in das Labyrinth des Majotauris, innerhalb einer Schallplattenrille der Schallplatte "Kleines Harmonisches Labyrinth" von Bach. Sie fallen in eine Grube und finden dort Pop-Corn, mit dessen Hilfe sie sich wieder in das Escherbild "Reptilien" hineinpoppen. Dieses Bild verlassen sie indem sie senkrecht zur Bildebene klettern. Schließlich landen sie im Haus des Herrn S.

    Ende.

    <Inhalt>
     

    3: Rekursion, allgemeine Definition:

    Eine allgemeine Definition ist in sofern schwierig, da man auch Rekursion rekursiv definieren kann. Deswegen ist es besser Rekursion an Beispielen zu erläutern.

    Hofstadter selbst defieniert Rekursion wie folgt: Verschachtelung und Varianten von Verschachtelungen,(Geschichten innerhalb von Geschichten, Filme innerhalb von Filmen, Gemälden innerhalb von Gemälden, russische Puppen innerhalb von russischen Puppen (sogar Kommentare in Klammern innerhalb von Kommentaren in Klammern)).
    Im Internet fand ich eine schöne Definition von Rekursion:

    Ein Objekt heißt rekursiv, wenn es durch sich selbst definiert ist, oder sich selbst (ganz oder teilweise) enthält.

    Ein gutes Beispiel ist die Benutzung einer Telefonanlage mit Umleitungsfunktion. Ein Manager sitzt im Büro und erhält einen Anruf von Anrufer A. Er unterhält sich einige Zeit mit ihm, plötzlich bekommt er ein Anruf auf Leitung B. "Warten sie einen Augenblick bitte", sagt er zu Anrufer A und schaltet zu Anrufer B. Wenig später wechselt er noch zu einem Anrufer C, beendet das Gespräch mit ihm, wechselt wieder zu Anrufer B und beendet auch dieses Gespräch. Dann will der Manager wieder mit Anrufer A sprechen, aber da kommt Anrufer D dazwischen. Erst als er dieses Gespräch beendet hat, kann sich der Manager wieder Anrufer A widmen.

    Dieses Beispiel zeigt zum einen gut eine Spielart der Rekursion. Zum Zweiten ist dieses Beispiel gar nicht so unrealistisch wie es scheint. Man kann es analog übertragen auf ein Beispiel im Untericht: Die Schüler sind mit einer Einzelaufgabe beschäftigt, der Lehrer sitzt als Ansprechperson im Raum. Schülerin A kommt mit einem größeren Problem zu ihm. Währenddessen kommen andere Schüler auf ihn zu und haben kleinere und größere Fragen. Der Lehrer muß sich jetzt ein System aussuchen, in welcher Reihenfolge er die Anfragen behandelt.

    An dieser Stelle definiere ich noch kurz drei Begriffe:
    pushen: Man unterbricht die Aufgabe, mit der man sich gerade beschäftigt, merkt sich wo man aufgehört hat und fängt eine neue Aufgabe an. Diese neue Aufgabe steht auf einer tieferen Stufe als die erste.
    poppen: man schließt eine Aufgabe der unteren Stufe ab, und kehrt zurück zu höheren Aufgabe.
    Stappel: Information, auf welcher Stufe man sich befindet und der Zustand der einzelnen Stufen.

    Man kann rekursive Sachverhalte durch sogenannte Rekursive Transitions-Netzwerke kurz RTN darstellen. Ein RNT ist ein Diagramm, das verschiedene Wege zeigt, denen man bei der Erledigung einer bestimmten Aufgabe folgen kann. Jeder Weg besteht aus einer gewissen Anzahl von Knoten die durch Pfeile miteinander verbunden sind.

    <Inhalt>

    4: Beispiele:

    4.1: Rekursion in der Musik:

    Wir hören Musik rekursiv. Im Kopf haben wir einen Stapel von Tonarten und jede neue Modulation pusht eine neue Tonart auf dem Stapel.Wir wollen die Reihe der Tonarten in umgekehrter Reihenfolge hören, d.h die gepushten Tonarten hinunterpoppen bis die Tonika ereicht ist.

    4.2: Rekursion in der Sprache:

    In der Sprache ist unsere Fähigkeit Stapel zu bilden noch stärker. Die grammatikalische Struktur aller Sprachen bedingt, daß man recht kompliezierte push-down-Stapel herstellen kann, obwohl die Schwierigkeit einen Satz zu verstehen, mit der Anzahl der Push auf einem Stapel rapide zunimmt. Besonders in der deutschen Sprache kann man aufgrund der Tatsache, daß das Hauptverb an Satzende gestellt wird, rekursive Sätze konstruieren.

    Jede Sprache weist Konstruktionen auf, die Stapel benötigen, wenn auch im Allgemeinen nicht so spektakulär wie im Deutschen.
     
     
     
     
     

    4.3: rekursive Folgen:

    Rekursive Folgen, sind Folgen, in denen um den Wert eines Folgengliedes auszurechnen, die voherigen Werte bekannt sein müssen. Man pusht sich quasi immer tiefer in den Stapel hinein bis man auf bekannte Werte trifft.
    Die bekannteste rekursive Folge ist die Fibonacci-Folge, die die Fibonacci-Zahlen erzeugen. Sie sind im Jahre 1202 von Leonardo von Pisa entdeckt worden.

    4.4: rekursives Programmieren

    Rekursives Programmieren gehört zu den Standard in den modernen Programmiersprachen. Mit Hilfe von Schleifen kann man Programmstrukturen schachteln. Quasi kann man alle Computerprogramme, die mathematische Berechnungen durchführen oder mit mathematischen Werten arbeiten lassen, denn der Computer kann sich mit unvorstellbaren Geschwindigkeiten durch die Stapel pushen oder poppen. Standardbeispiele für Rekursionsprogramme sind z.B. Primzahlentests oder Programme mit Flußvariablen (Die Variablen verändern sich nach gewissen Regeln). Meistens werden beim rekursiven Programmieren Funktionen und Prozeduren konstruiert, die sich selbst aufrufen.

    4.5: Rekursion beim Schach:
    Alle 2-Personen Nullsummenspiele mit vollständiger Information besitzen auch einen Satz der Spieltheorie eine optimale Spieltaktik um zu gewinnen oder ein Unentschieden zu sichern. ( Beim Schach ist es bislang ungeklärt, was man mit einer optimalen Taktik erreicht. Zwar gibt es eine, aber kein Mensch weiß bisher wie sie aussieht.) Allerdings wird die optimale Taktik um so komplizierter, je mehr das Spiel komplexer wird. Eine gute Taktik beim Schach, die von allen guten Spielern benutzt wird, ist es die Züge seines Gegners vorauszuberechnen. (Wenn ich so, dann er so, daraufhin ich...). Die besten Spieler sind in der Lage bis zu sechs Züge des Gegners (und damit 12 insgesamt) vorauszuberechnen.
    Was ist nun der rekursive Charakter dieser Strategie ? Der Spieler muß davon ausgehen, daß sein Gegner den bestmöglichen Zug machen wird, daß heißt er muß in dessen Rolle schlüpfen, und beurteilen, wie er ziehen würde. Dazu muß er aber die Züge seines Gegners (also in Wirklichkeit seine eigenen Züge vorausrechnen). Wenn es also eine Funktion 'bester Zug' gäbe, könnte sie so aussehen: Reaktion auf bester Zug (Gegner) bester Zug (Gegner)=Reaktion auf bester Zug (Selbst). Der rekursive Charakter dieser Situation liegt auf der Hand.


    <Inhalt>

    5 Ausblick - Bedeutung der Rekursion in der Pädagogik

    Zuerst muß zwischen zwei Rekursionsarten unterschieden werden, die frei und die gebundene Rekursion. Mathematische Rekursionsformeln sind immer gebunden, da der Benutzer sich an die Algorithmen der Formel halten muß. Die Formel bestimmt Abbruchbedingungen, Bildung der Stapel, den Zeitpunkt des Pushens und Poppens u.s.w. Dagegen ist in der freien Rekursion dem Benutzer freigestellt was er in welcher Reihenfolge und wie macht. Im Beispiel mit dem Telefonrufumleiten hätte sich der Manager auch anders entscheiden können, z.B. nach Wichtigkeit des Gesprächspartners (er schickt Anrufer 1 auf Warteleitung, unterbricht aber nicht das Gespräch mit Anrufer zwei für Anrufer 3, sondern er telefoniert zu Ende und nimmt dann das Gespräch mit Anrufer 1 wieder auf und beendet erst am Schluß das Telefonat mit Anrufer 3). Ob Rekursionen frei oder gebunden sind erkennt man an den zugehörigen RNT's. Wenn man sich an den Knotenpunkten entscheiden kann oder muß, welchen Weg man weiter verfolgt, ist die Rekursion frei. Ist der weitere Weg aber bereits durch den vorherigen Weg bestimmt (wie das bei mathematischen Formeln der Fall ist), ist die Rekursion gebunden. In der Pädagogik sollte meiner Meinung nach nur freie Rekursionen zum Einsatz kommen. Im folgenden ein Beispiel für eine rekursive Unterrichtsstunde:

    Im Mathematikunterricht werden gerade die Pythagorassätze für Dreiecke behandelt. An dieser Stelle pusht der Lehrer zum ersten Mal und erzählt der Klasse erwas über Pythagoras und seine Zeit. Da fragt ein Schüler etwas über einen griechischen Gott. Es erfolgt der zweite Push. Die Klasse beginnt über griechische Mythologie und Geschichte zu diskutieren. Irgendwann, die Klasse ist mittlerweile beim Mittelalter angekommen, beschließt der Lehrer wieder mathematische Inhalte in den Vordergrund zu rücken. Er stellt den Schülern Fibonacci und dessen Folge vor. Zum Schluß poppt er wieder zum Anfang des Unterrichtes, zu den Dreiecken zurück. Jeder Pädagoge muß selbst entscheiden inwieweit er diesen Unterrichtsstil, freie Assoziation (die wird von vielen Lehrern am Anfang einer Unterrichtseinheit gestellt "Was stellt ihr euch vor unter dem Begriff....?") oder ähnliches zuläßt, Aber auch kurzzeitige Exkursionen im Frontalunterricht, Auslassungen des Lehrers, die nichts direkt mit dem Thema zu tun haben, mit dem Ziel den Schülern das Verständnis zu erleichtern, sind eine Form rekursiven Unterrichts.

    Rekursiver Unterricht ist als bewußt eingesetztes Mittel im Unterricht sicherlich sinnvoll im Verständnis und Motivation beim Schüler zu weckern und ihn den Einstief zu erleichtern. Wie bei allen anderen Dingen auch, ist hier die Dosis entscheidend. Ein zuviel ist auch hier schädlich. Wenn der Lehrer rekursive Unterrichtsmethoden unreflektiert und nur mit dem Ziel eigener Arbeitsersparnis ohne ausreichende Vorbereitung anwendet kann das ziemlich schief gehen.

     <Inhalt>


    Einstiegsseite