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

solchen Algorithmus in BlooP im Wege steht? Und wie steht es mit derselben Frage im Hinblick auf die Eigenschaft der im Dialog definierten „Wundersamkeit“?
    Nachstehend führe ich einige Funktionen und Eigenschaften auf, und Sie sollten sich die Zeit nehmen, festzustellen, ob Sie glauben, daß sie primitiv-rekursiv (BlooP-programmierbar) sind oder nicht. Das bedeutet, daß Sie sorgfältig erwägen müssen, welche Arten von Operationen in den nötigen Berechnungen involviert sind, und ob für alle Schleifen Obergrenzen angegeben werden können.
    FAKULTÄT [N] = N! ( N Fakultät)
(z. B.
FAKULTÄT [4] = 24 )
    REST [M, N] = der Rest bei der Division von M durch N
(z. B.
REST [24, 7] = 3 )
    PI-ZIFFER [N] = die N -te Ziffer von π nach dem Komma
(z. B.
PI-ZIFFER [1] = 1 ,
PI-ZIFFER [2] = 4 ,
PI-ZIFFER [1000000] = 1 )
    FIBO [N] = die N -te Fibonaccizahl
(z. B.
FIBO [9] = 34 )
    PRIM-JENSEITS [N] = die niedrigste Primzahl größer als N
(z. B.
PRIM-JENSEITS [33] = 37 )
    PERFEKT [N] = die N -te „perfekte“ Zahl (eine Zahl wie z. B. 28, deren Teiler, wennaddiert, die Zahl selber ergeben: 28 = 1 + 2 + 4 + 7 + 14)
(z. B.
PERFEKT [2] = 28 )
    PRIM? [N] = JA wenn N prim, sonst NEIN .
    PERFEKT? [N] = JA wenn N perfekt, sonst NEIN .
    TRIVIAL? [A, B, C, N] = JA wenn A N + B N = C N richtig ist, sonst NEIN .
(z. B.
TRIVIAL? [3, 4, 5, 2] = JA ,
TRIVIAL? [3, 4, 5, 3] = NEIN )
    PIERRE? [A, B, C] = JA wenn A N + B N = C N eine Lösung für N größer als 1 hat, sonst NEIN .
(z. B.
PIERRE? [3, 4, 5] = JA ,
PIERRE? [1, 2, 3] = NEIN )
    FERMAT? [N] = JA wenn A N + B N = C N durch positive Werte von A , B , C erfüllt werden kann, sonst NEIN .
(z. B.
FERMAT? [2] = JA )
    SCHILDKRÖTENPAAR? [M, N] = JA wenn sowohl M wie auch M + N prim sind, sonst NEIN .
(z. B.
SCHILDKRÖTENPAAR? [5, 1742] = JA ,
SCHILDKRÖTENPAAR? [5, 100] = NEIN )
    SCHILDKRÖTE? [N] = JA wenn N die Differenz zweier Primzahlen ist, sonst NEIN .
(z. B.
SCHILDKRÖTE? [1742] = JA ,
SCHILDKRÖTE? [7] = NEIN )
    MIU-WOHLGEFORMT? [N] = JA wenn N , verstanden als Kette im MIU-System, wohlgeformt ist, sonst NEIN .
(z. B.
MIU-WOHLGEFORMT? [310] = JA ,
MIU-WOHLGEFORMT? [415] = NEIN )
    MIU-BEWEISPAAR? [M, N] = JA wenn M , verstanden als eine Folge von Ketten im MIU-System eine Ableitung von N ist, ebenfalls verstanden als eine Kette im MIU- System, sonst NEIN .
(z. B.
MIU-BEWEISPAAR? [3131131111301, 301] = JA ,
MIU-BEWEISPAAR? [311130, 30] = NEIN )
    MIU-SATZ? [N] = JA wenn N , verstanden als eine Kette im MIU-System, ein S ATZ ist, sonst NEIN .
(z. B.
MIU-SATZ? [311] = JA ,
MIU-SATZ? [30] = NEIN ,
MIU-SATZ? [701] = NEIN )
    TNT-SATZ? [N] = JA wenn N , verstanden als eine TNT-Kette, ein S ATZ ist.
(z. B.
TNT-SATZ? [666111666] = JA ,
TNT-SATZ? [123666111666] = NEIN ,
TNT-SATZ? [7014] = NEIN )
    FALSCH? [N] = JA wenn N , verstanden als TNT-Kette, eine falsche Aussage der Zahlentheorie ist, sonst NEIN .
(z. B.
FALSCH? [666111666] = NEIN ,
FALSCH? [223666111666] = JA ,
FALSCH? [7014] = NEIN )
    Die letzten sieben Beispiele sind besonders wichtig für unsere bevorstehenden meta-mathematischen Untersuchungen; sie verdienen also besondere Aufmerksamkeit.
Ausdrückbar und repräsentierbar
    Bevor wir nun zu interessanten Fragen über BlooP und zu seinem Verwandten FlooP kommen, kehren wir zu der Frage zurück, warum wir BlooP überhaupt eingeführt haben, und stellen eine Verbindung zu TNT her. Ich habe bereits früher gesagt, daß die kritische Masse für die Anwendung der Gödelschen Methode dann erreicht ist, wenn alle primitiv-rekursiven Begriffe in diesem System repräsentierbar sind. Was heißt das genau? Zunächst müssen wir zwischen dem Begriff der Repräsentierbarkeit und dem der Ausdrückbarkeit unterscheiden. Ein Prädikat ausdrücken ist einfach eine Übersetzung aus dem Deutschen in einen strikten Formalismus. Ob es sich um S ÄTZE handelt, hat damit nichts zu tun. Die Repräsentierung eines Prädikats dagegen ist ein weit stärkerer Begriff. Er bedeutet, daß
1)
alle Fälle, in denen die Prädikate wahr sind, S ÄTZE sind;
2)
alle Fälle, in denen sie falsch sind, Nicht-S ÄTZE sind.
    Mit „Fall“ meine ich die Kette, die erzeugt wird, wenn man alle freien Variablen durch Zahlzeichen ersetzt. Zum Beispiel ist das Prädikat m + n = k im pg-System repräsentiert, weil jeder wahre Fall des Prädikats ein S ATZ ist, und jeder falsche ein Nicht-S ATZ . So läßt sich jede einzelne Addition, ob wahr oder falsch, in eine entscheidbare Kette des pg-Systems übersetzen. Indessen ist das