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

Strukturebenen aufweist und deshalb unmöglich genau auf irgendeine finite Weise beschrieben werden kann (siehe B. Mandelbrots Buch Fraktals). Das Spiegelbild des Baums stellt die Menge der Verneinungen von Sätzen dar: alle falsch, aber dennoch alle zusammen nicht fähig, den Bereich der falschen Aussagen völlig zu decken. [Zeichnung des Verfassers.]
Figur und Hintergrund in der Musik
    Man kann sich auch in der Musik nach Figur und Hintergrund umsehen. Eine analoge Erscheinung ist die Unterscheidung von Melodie und Begleitung — die Melodie steht immer im Vordergrund unserer Aufmerksamkeit, und in einem gewissen Sinn ist dieBegleitung ihr untergeordnet. Deshalb ist es überraschend, wenn wir in den tieferen Stimmen erkennbare Melodien finden. In der Nach-Barockmusik geschieht das nicht allzu häufig. Im allgemeinen sind die Harmonien nicht als Vordergrund beabsichtigt. Aber in der Barockmusik — und vor allem bei Bach — dienen die verschiedenen Stimmen, ob hoch oder tief oder dazwischen, alle als „Figuren“: In diesem Sinn kann man Stücke von Bach „rekursiv“ nennen.
    In der Musik gibt es noch einen weiteren Unterschied zwischen Figur und Hintergrund: den zwischen betontem und unbetontem Taktteil. Wenn man die Noten im Takt „eins-und, zwei-und, drei-und, vier-und“ zählt, fallen die meisten Noten der Melodie auf Zahlen, nicht auf „und“. Mitunter wird jedoch eine Melodie absichtlich, einfach um der Wirkung willen, auf die verschiedenen „und“ verlegt. Das ist z. B. bei verschiedenen Etüden von Chopin der Fall. Es findet sich auch bei Bach, besonders in den Sonaten und Suiten für Violine solo und seinen Suiten für Cello solo. Bach bringt es hier fertig, zwei und mehr musikalische Stimmen gleichzeitig in Gang zu setzen. Manchmal tut er das, indem er die Soloinstrumente „Doppelgriffe“ — zwei Noten gleichzeitig — spielen läßt. In andern Fällen jedoch legt er eine Stimme auf die betonten und die andere auf die unbetonten Taktteile, so daß das Ohr sie trennt und zwei verschiedene Melodien hört, die sich ver- und entflechten und miteinander harmonieren. Natürlich machte Bach nicht auf dieser Komplexitätsebene halt ...
Rekursiv aufzählbare Mengen — rekursive Mengen
    Übertragen wir nunmehr die Begriffe „Figur“ und „Hintergrund“ wieder in den Bereich der formalen Systeme. In unserem Beispiel spielen die S ÄTZE vom Z-Typus die Rolle des positiven Raums, und Ketten mit einer Primzahl von Bindestrichen die des negativen. Bis jetzt war das einzige Mittel zur typographischen Darstellung von Primzahlen, das wir gefunden haben, der negative Raum. Gibt es jedoch eine Methode, und sei sie noch so kompliziert, die Gesamtheit der Primzahlen als positiven Raum darzustellen, d. h. als eine Menge von S ÄTZEN eines formalen Systems?
    Hier geben verschiedene Leute intuitiv verschiedene Antworten. Ich erinnere mich lebhaft daran, wie fasziniert und verblüfft ich war, als mir der Unterschied zwischen positiver und negativer Charakterisierung aufging. Ich war überzeugt davon, daß jede Menge von Zahlen, nicht nur die der Primzahlen, die negativ repräsentiert werden kann, sich auch positiv repräsentieren läßt. Die Intuition, auf die sich mein Glaube stützte, ist in der Frage enthalten: „Wie ist es möglich, daß eine Figur und ihr Hintergrund nicht genau dieselbe Information enthalten?“ Sie schienen mir die gleiche Information zu enthalten, die einfach auf zwei komplementäre Arten codiert war. Was halten Sie für richtig?
    Es stellte sich heraus, daß ich recht hatte, was Primzahlen angeht, unrecht aber im Allgemeinfall. Das erstaunte mich und erstaunt mich noch heute. In der Tat ist es so:
    Es gibt formale Systeme, deren negativer Raum (Menge der Nicht-S ÄTZE ) nicht den positiven Raum (Menge der S ÄTZE ) irgendeines formalen Systems bildet.
    Es zeigt sich, daß dieses Ergebnis von gleicher Tragweite wie Gödels Satz ist — es ist also nicht überraschend, daß meine Intuition Lügen gestraft wurde. Wie die Mathematiker im frühen zwanzigsten Jahrhundert erwartete ich von der Welt der formalen Systeme und der natürlichen Zahlen, daß sie besser voraussagbar sei, als sie es tatsächlich ist. In einer mehr technischen Terminologie wird daraus:
    Es gibt rekursiv aufzählbare Mangen, die nicht rekursiv sind.
    Der Ausdruck rekursiv aufzählbar („r. a.“) ist das mathematische Gegenstück zu unserer Vorstellung „kursiv zeichenbar“ in der Kunst, und rekursiv ist das