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

Wichtig ist es, weil es ein vortreffliches Beispiel für viele Gedanken bietet, die in diesem Buch eine wichtige Rolle spielen. Im pg-System gibt es drei verschiedene Symbole:
    p  g  −
    — die Buchstaben p und g und den Bindestrich.
    Das pg-System hat eine unendliche Anzahl von Axiomen. Da wir sie nicht alle niederschreiben können, müssen wir eine andere Methode haben, um sie zu beschreiben. Tatsächlich wollen wir ja mehr als einfach eine Beschreibung der Axiome; wir wollen eine Methode, die uns erlaubt, festzustellen, ob eine bestimmte Kette ein Axiom ist oder nicht. Eine bloße Beschreibung der Axiome könnte sie vielleicht vollständig, aber eben doch nur schwach charakterisieren — das war ja das Problem bei der Charakterisierung der Sätze im MIU-System. Wir wollen uns nicht eine unbestimmte, möglicherweise unendlich lange Zeitspanne damit abquälen, herauszufinden, ob einegewisse Kette ein Axiom ist oder nicht. Deshalb werden wir die Axiome so definieren, daß ein offensichtliches Entscheidungsverfahren dafür existiert, ob eine aus p 's, g 's und Bindestrichen bestehende Kette ein Axiom ist.
    D EFINITION : x p−g x − ist ein Axiom, wenn x nur aus Bindestrichen besteht.
    Beachten Sie, daß „ x “ beide Male für die gleiche Kette von Bindestrichen stehen muß. Z. B. ist −−p−g−−− ein Axiom. Der Ausdruck „x p−g x − “ ist natürlich kein Axiom (weil „ x “ nicht zum pg-System gehört); es ist eher eine Form, in die alle Axiome gegossen werden, und heißt Axiomen-Schema.
    Das pg-System besitzt nur eine einzige Erzeugungsregel:
    R EGEL : Angenommen x, y und z stehen alle für einzelne Ketten, die nur Bindestriche enthalten, und angenommen, daß man weiß, daß x p y g z ein S ATZ ist. Dann ist x p y −g z − ein Satz.
    Nehmen wir z. B. x als „ −− “, y als „ −−− “, und z als „ − “. Die Regel sagt uns:
    Wenn −−p−−−g− sich als S ATZ erweist, dann auch −−p−−−−g−− .
    Wie das für die Erzeugungsregeln typisch ist, bedeutet diese Aussage eine Kausalverknüpfung zwischen zwei Ketten in ihrer Eigenschaft als S ÄTZE , ohne aber zu behaupten, daß jede einzelne von ihnen allein ein S ATZ sei.
    Eine äußerst nützliche Übung ist die, ein Entscheidungsverfahren für die S ÄTZE des pg-Systems zu finden. Schwierig ist das nicht, wenn Sie eine Zeitlang damit gespielt haben, kommen sie wahrscheinlich darauf. Versuchen Sie es.
Das Entscheidungsverfahren
    Ich nehme an, Sie haben's versucht. Zunächst möchte ich, auch wenn es zu offensichtlich scheint, als daß man es erwähnen müßte, darauf hinweisen, daß jeder S ATZ des pg-Systems drei verschiedene Gruppen von Bindestrichen enthält und daß die trennenden Elemente ein p und ein g — in dieser Reihenfolge — sind. (Man kann das mit einem auf „Vererblichkeit“ beruhenden Beweisgang zeigen, genauso wie wir zeigen konnten, daß alle S ÄTZE des MIU-Systems mit M beginnen müssen.) Das bedeutet, daß wir rein aus formalen Gründen eine Kette wie −−p−−p−−p−−g−−−−−−−− ausschalten können.
    Nun mag es albern erscheinen, den Ausdruck „rein aus formalen Gründen“ zu betonen. Was besitzt eine Kette anderes als ihre Form? Was könnte sonst noch bei der Bestimmung ihrer Eigenschaften eine Rolle spielen? Offensichtlich nichts. Denken Sie aber während der Diskussion formaler Systeme daran: der Begriff der „Form“ wird immer komplizierter und abstrakter werden, und wir werden über die Bedeutung des Wortes „Form“ noch mehr nachdenken müssen. Nennen wir also jede Kette, die mit einer Gruppe von Bindestrichen beginnt, auf die dann ein p , eine zweite Bindestrichgruppe sowie ein g folgt und die mit einer letzten Bindestrichgruppe aufhört, eine wohlgeformte Kette.
    Zurück zum Entscheidungsverfahren ... Das Kriterium dafür, daß ein S ATZ vorliegt, ist, daß sich die Bindestrichlängen der ersten beiden Gruppen zu der der dritten addieren. Z. B. ist −−p−−−g−−−−− ein S ATZ , da 2 plus 2 4 gibt, während −−p−−g− keiner ist, da 2 plus 2 ungleich 1 ist. Um zu erkennen, daß das wirklich ein Kriterium ist, betrachten wir zuerst das Axiomen-Schema. Offensichtlich erzeugt es nur Axiome, die diesem Kriterium der Addition genügen. Man betrachte sodann die Erzeugungsregel: Wenn die erste Kette dem Additionskriterium genügt, dann muß es auch die zweite tun — und umgekehrt, wenn die erste Kette ihm nicht genügt, tut es auch die