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:

.
.
.
.
    Früher oder später erzeugt dieses Vorgehen jeden einzelnen S ATZ , weil die Regeln in jeder möglichen Reihenfolge angewendet wurden (siehe Abb. 11). Irgendwann einmal werden alle die erwähnten Verlängerungen und Verkürzungen ausgeführt sein. Indessen ist nicht klar, wie lange man darauf warten muß, bis eine bestimmte Kette in dieser

    Abb. 11 . Ein systematisch konstruierter „Baum“ aller SÄTZE des MIU-Systems. Die N-te Stufe von oben enthält jene S ÄTZE , deren Ableitungen genau N Schritte umfassen. Die Ziffern in den Ringen geben an, welche Regeln angewendet wurden. Ist MU irgendwo in diesem Baum?
    Liste erscheint, da die S ÄTZE gemäß der Kürze ihrer Ableitung aufgeführt werden. Wenn man an einer besonderen Kette, wie z. B. MU interessiert ist, und nicht einmal weiß, ob sie überhaupt abgeleitet werden kann, und noch viel weniger, wie lang diese Ableitung sein könnte, ist das keine sehr brauchbare Anordnung.
    Wir geben nunmehr den „S ATZ heit-Test“:
    Warten Sie, bis die fragliche Kette hergestellt ist; wenn das geschieht, wissen Sie, daß sie ein S ATZ ist — und wenn es nie geschieht, wissen Sie, daß sie kein S ATZ ist.
    Auf den ersten Blick ist das lächerlich, denn es setzt voraus, daß wir bereit sind, buchstäblich unendlich lange auf unsere Antwort zu warten. Das bringt uns zum Kern der Frage, was als „Test“ gelten soll. Von entscheidender Wichtigkeit ist eine Garantie, daß wir unsere Antwort in einem endlichen Zeitabschnitt erhalten. Wenn es einen Test für S ATZ heit gibt, einen Test, der immer in einer endlichen Zeitspanne ein Ende findet, dann nennt man diesen Test ein Entscheidungsverfahren für das vorliegende formale System.
    Wenn Sie über ein Entscheidungsverfahren verfügen, dann haben Sie eine sehr konkrete Charakterisierung aller S ÄTZE in dem System. Auf den ersten Blick könnte man vielleicht meinen, daß die Regeln und Axiome des formalen Systems eine nicht weniger vollständige Charakterisierung der S ÄTZE des Systems liefern als ein Entscheidungsverfahren. Das heikle Wort ist hier „Charakterisierung“. Gewiß charakterisieren die Schlußregeln und Axiome des MIU-Systems implizit diejenigen Ketten, die S ÄTZE sind. Sogar noch impliziter charakterisieren sie die Ketten, die nicht S ÄTZE sind. Aber implizite Charakterisierung genügt für viele Zwecke nicht. Wenn jemand behauptet, daß er eine Charakterisierung aller S ÄTZE besitze, aber unendlich viel Zeit zu dem Schluß braucht, daß eine gewisse Kette kein S ATZ ist, wäre man wohl geneigt zu sagen, daß etwas an dieser Charakterisierung fehlt. Sie ist nicht konkret genug. Und aus diesem Grunde ist es ein sehr wichtiger Schritt, herauszufinden, ob es ein Entscheidungsverfahren gibt. Was diese Entdeckung tatsächlich bedeutet, ist, daß man einen Test darüber durchführen kann, ob eine Kette einen S ATZ darstellt und daß der Test, auch wenn er kompliziert ist, garantiert ein Ende findet. Prinzipiell ist der Test genauso leicht, genauso mechanisch, genauso finit, genauso sicher, wie die Prüfung, ob der erste Buchstabe der Kette M ist. Ein Entscheidungsverfahren ist ein „Lackmus-Test“ für S ÄTZE .
    Übrigens ist es eine Bedingung für formale Systeme, daß das Bündel von Axiomen durch ein Entscheidungsverfahren gekennzeichnet ist — es muß einen Lackmus-Test für Axiomheit geben. Das gewährleistet, daß man zumindest am Anfang ohne weiteres in Gang kommen kann. Das ist der Unterschied zwischen der Menge der Axiome und der Menge der S ÄTZE ; die erste hat immer ein Entscheidungsverfahren, die letzte braucht keines zu haben.
    Sie werden sicher zugeben, daß Sie sich beim ersten Blick auf das MIU-System genau diesem Problem gegenübersahen. Das einzige Axiom war bekannt, die Schluß-Regeln waren einfach, so waren die S ÄTZE also implizit charakterisiert — und doch war es noch immer ganz unklar, was die Konsequenzen dieser Charakterisierung waren. Insbesondere war noch völlig unklar, ob MU ein S ATZ ist oder nicht.

Zweistimmige Invention
    oder
    Was die Schildkröte zu Achilles sagte
    von Lewis Carroll 1
    Achilles hatte die Schildkröte eingeholt und sich gemütlich auf ihrem Rücken niedergelassen.
    „So haben wir also das Ende unserer Rennbahn erreicht?“, sagte die Schildkröte. „Obgleich sie TATSÄCHLICH aus einer unendlichen Reihe von Abständen besteht? Ich dachte, irgend so ein ganz Schlauer hätte bewiesen, daß es unmöglich sei?“
    „Es IST möglich“, sagte