Bücher online kostenlos Kostenlos Online Lesen
Gödel, Escher, Bach - ein Endloses Geflochtenes Band

Gödel, Escher, Bach - ein Endloses Geflochtenes Band

Titel: Gödel, Escher, Bach - ein Endloses Geflochtenes Band Kostenlos Bücher Online Lesen
Autoren: Douglas R. Hofstadter
Vom Netzwerk:
natürlich nicht 0, sondern NEIN .
    Sehen wir uns ein Beispiel für diese letzten beiden BlooP-Eigenschaften in einem Algorithmus an, der die Primzahl-Eigenschaft testet.
    PROZEDURDEFINITION „PRIM?“ [N]:
    BLOCK 0: ANFANG
    WENN N = 0, DANN:
    BEENDE BLOCK 0;
    ZELLE (0)2;
    SCHLEIFE HÖCHSTENS MINUS [N,2] MAL:
    BLOCK 1: ANFANG
    WENN REST [N, ZELLE(0)] = 0, DANN:
    BEENDE BLOCK 0;
    ZELLE (0)ZELLE (0) + 1;
    BLOCK 1: ENDE;
    OUTPUTJA;
    BLOCK 0: ENDE.
    Man beachte, daß ich zwei Prozeduren innerhalb dieses Algorithmus aufgerufen habe: MINUS und REST . (Vom letzteren kann man annehmen, daß es schon früher definiert worden ist, und der Leser kann die Definition selbst herausfinden.) Dieser Test für die Primzahl-Eigenschaft geht nun so vor sich, daß man die potentiellen Faktoren von N nacheinander ausprobiert. Man beginnt mit 2 und macht bis zum Maximum von N - 1 weiter. Falls einer von ihnen genau in N aufgeht (d. h. den Rest 0 ergibt), springen wir zum unteren Ende, und da OUTPUT in diesem Stadium noch immer seinen „Default“-Wert besitzt, ist die Antwort NEIN . Nur wenn N keinen Teiler besitzt, wird es SCHLEIFE 1 zur Gänze überleben, dann werden wir ohne Schwierigkeiten zur Aussage OUTPUT  JA geraten. Sie wird ausgeführt, dann ist die Prozedur zu Ende.
BlooP-Programme enthalten Ketten von Prozeduren
    Wir haben gesehen, wie man Prozeduren in BlooP definiert; doch ist eine Prozedurdefinition nur ein Teil eines Programms. Eine Programm besteht aus einer Kette von Prozedurdefinitionen (von denen jede nur bereits früher definierte Prozeduren aufruft), worauf wahlweise eine oder mehrere der definierten Prozeduren folgen. Ein Beispiel für ein volles BlooP-Programm wäre die Definition der Prozedur ZWEI-HOCH-DREI-HOCH, gefolgt vom Aufruf
    ZWEI-HOCH-DREI-HOCH [2]
    und das ergäbe als Antwort 512.
    Hat man nur eine Kette von Prozedurdefinitionen, geschieht überhaupt nichts. Sie warten alle darauf, mit speziellen numerischen Werten aufgerufen zu werden, um sich in Bewegung zu setzen. Es ist wie ein Fleischwolf, der auf Fleisch wartet, das er zerhacken kann, oder vielmehr eine Kette von Fleischwölfen, die alle miteinander verbunden sind, so daß jeder von den vorhergehenden gespeist wird. Im Falle von Fleischwölfen ist das Bild vielleicht nicht so appetitlich, aber im Fall der BlooP-Programme ist eine solche Konstruktion einigermaßen wichtig, und wir wollen sie ein „aufrufloses Programm“ nennen. Diesen Begriff illustriert Abb. 72.

Abb. 72 . Die Struktur eines aufruflosen BlooP-Programms. Damit dieses Programm in sich geschlossen ist, kann jede Prozedurdefinition nur solche über sich aufrufen.
    Nun ist BlooP unsere Sprache für die Definition voraussagbar endender Berechnungen. Der übliche Name für BlooP-berechenbare Funktionen ist primitiv-rekursive Funktion, und der übliche Name für Eigenschaften, die durch BlooP entdeckt werden können, ist primitiv-rekursive Prädikate. So ist also die Funktion 2 3 n eine primitiv-rekursive Funktion, und die Aussage „n ist eine Primzahl“ ist ein primitiv-rekursives Prädikat.
    Es ist intuitiv klar, daß die Goldbach-Eigenschaft primitiv-rekursiv ist, und um das ganz klar zu machen, folgt hier eine Prozedurdefinition in BlooP, die zeigt, wie man ihr Vorhandensein oder nicht-Vorhandensein testen kann.
    PROZEDURDEFINITION „GOLDBACH?“ [N]:
    BLOCK 0: ANFANG
    ZELLE (0)2;
    SCHLEIFE HÖCHSTENS N MAL:
    BLOCK 1: ANFANG
    WENN {PRIM? [ZELLE (0)]
    UND PRIM? [MINUS [N, ZELLE (0)]]},
    DANN:
    BLOCK 2: ANFANG
    OUTPUT = JA;
    BEENDE BLOCK 0;
    BLOCK 2: ENDE
    ZELLE (0)ZELLE (0) + 1;
    BLOCK 1: ENDE;
    BLOCK 0: ENDE.
    Wie immer nehmen wir NEIN an, bis JA bewiesen ist, und wir suchen nach Zahlenpaaren, die addiert N ergeben. Sind beide Primzahlen, dann beenden wir den äußersten Block; sonst gehen wir einfach zurück und versuchen es noch einmal, bis alle Möglichkeiten erschöpft sind.
    (Warnung: Die Tatsache, daß die Goldbach-Eigenschaft primitiv-rekursiv ist, macht die Frage „Haben alle Zahlen die Goldbach-Eigenschaft?“ nicht einfach — bei weitem nicht!)
Vorschläge für Übungen
    Können Sie eine ähnliche BlooP-Prozedur schreiben, die das Vorhandensein oder Nicht-Vorhandensein der Schildkröten-Eigenschaft (oder der Achilles-Eigenschaft) testet? Wenn ja, tun Sie es. Wenn nein, dann rührt das daher, daß Sie über Obergrenzen nicht Bescheid wissen — oder könnte es möglicherweise daher kommen, daß es ein grundsätzliches Hindernis gibt, welches der Formulierung eines

Weitere Kostenlose Bücher