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:

Gegenstück zu „rekursiv“. Wenn eine Menge von Ketten „r. a.“ ist, so bedeutet das, daß sie nach typographischen Regeln erzeugt werden kann — z. B. die Menge der S ÄTZE des Z-Typus, die Menge der S ÄTZE des MIU-Systems, und darüber hinaus die Menge der S ÄTZE in jedem beliebigen formalen System. Das läßt sich vergleichen mit der Vorstellung von einer „Figur“ als einer „Menge von Strichen, die sich nach künstlerischen Regeln erzeugen läßt“ (was das immer heißen mag!). Und eine „rekursive Menge“ ist wie eine Figur, deren Hintergrund ebenfalls eine Figur ist — nicht nur sie ist r.a., sondern ihr Komplement ist ebenfalls r. a.
    Aus dem obigen Resultat ergibt sich:
    Es gibt formale Systeme, für die es keine typographischen Entscheidungsverfahren gibt.
    Wie kommt man zu diesem Schluß? Sehr einfach. Ein typographisches Entscheidungsverfahren ist eine Methode zur Unterscheidung von S ÄTZEN und Nicht-S ÄTZEN . Gibt es einen solchen Test, so gestattet er uns, systematisch alle Nicht-S ÄTZE zu erzeugen, indem wir einfach die Liste aller Ketten durchgehen, den Test auf jede einzelne Kette anwenden, und dabei alle nicht wohlgeformten Ketten und S ÄTZE ausmerzen. Das ist gleichbedeutend mit einer typographischen Methode, die Menge von Nicht-S ÄTZEN zu erzeugen. Aber gemäß einer früheren Feststellung (die wir hier unbewiesen akzeptieren) ist das in gewissen Systemen nicht möglich. Wir müssen also folgern, daß typographische Entscheidungsverfahren nicht für alle formalen Systeme existieren.
    Angenommen, wir fänden eine Menge F der natürlichen Zahlen („F“ steht für „Figur“), die wir mit einer bestimmten formalen Methode erzeugen können — wie etwa die zusammengesetzten Zahlen. Angenommen, ihr Komplement sei die Menge G (für „Grund“) — wie die Primzahlen. Zusammen bilden F und G alle natürlichen Zahlen, und wir kennen wohl eine Regel zur Erzeugung aller Zahlen der Menge F, aber keine, um alle Zahlen der Menge G zu erzeugen. Es ist wichtig, einzusehen, daß, wenn die Elemente von F immer nach zunehmender Größe erzeugt werden, wir G immer charakterisieren könnten. Das Problem liegt darin, daß viele rekursiv aufzählbare Mengen durch Methoden erzeugt werden, die die Elemente in eine willkürliche Ordnung bringen, so daß man nie weiß, ob eine Zahl, die längere Zeit übergangen worden ist, nicht doch aufgenommen wird, wenn wir nur noch etwas warten.
    Auf die Frage: „Sind in der Kunst alle Figuren rekursiv?“ haben wir mit „nein“ geantwortet. Jetzt erkennen wir, daß wir analoge Fragen in der Mathematik — „sind alle Mengen rekursiv?“ — ebenfalls verneinen müssen. Wenden wir uns unter diesemGesichtspunkt wieder dem schwer zu fassenden Wort „Form“ zu. Nehmen wir nochmals unsere Figurenmenge F und unsere Grundmenge G. Wir können uns dahingehend einigen, daß alle Zahlen in der Menge F eine gemeinsame „Form“ haben — läßt sich aber das gleiche von den Zahlen der Menge G sagen? Eine seltsame Frage. Wenn wir es von Anfang an mit einer unendlichen Menge — den natürlichen Zahlen — zu tun haben, dann kann es sehr schwierig sein, die durch die Entfernung einer Teilmenge entstandenen Löcher explizit zu definieren. Und so sind sie möglicherweise nicht durch eine gemeinsame Eigenschaft oder „Form“ miteinander verbunden. Im Grunde ist es Geschmacksache, ob man das Wort „Form“ verwenden will — aber schon darüber nachzudenken ist anregend. Vielleicht ist es am besten, „Form“ nicht zu definieren, sondern dem Wort eine gewisse intuitive Verschwommenheit zu belassen.
    Hier ein Rätsel, über das man im Zusammenhang mit den obigen Gedankengängen nachdenken möge. Können Sie die folgende Menge von natürlichen Zahlen (oder ihren negativen Raum) charakterisieren?
    1 3 7 12 18 26 35 45 56 69...
    Inwiefern ist diese Folge der F IGURE -F IGURE -Figur ähnlich?
Primzahlen als Figur anstatt als Hintergrund
    Schließlich: wie steht es mit einem formalen System zur Erzeugung von Primzahlen? Wie bringt man es zustande? Der Trick besteht darin, über die Multiplikation hinweg und direkt zu der Nichtteilbarkeit als dem positiv zu Repräsentierenden überzugehen. Im folgenden ein Axiomenschema und eine Regel zur Erzeugung von S ÄTZEN , die die Eigenschaft darstellen: eine Zahl ist kein Teiler ( IKT ) einer anderen (ohne Rest):
    A XIOMENSCHEMA : xy lKT x, wobei x und y Bindestrichketten sind.
    Zum Beispiel: −−−−−IKT−− , wobei x