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

verstehen; das „Alphabet“ umfaßt alle die speziellen Schriftzeichen von BlooP etwa in folgender willkürlicher Anordnung:
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
+
×
0
1
2
3
4
5
6
7
8
9

=
<
>
(
)
[
]
{
}
-
'
?
:
;
,
.
 
    Und am Ende kommt die demütige Leerstelle! Zusammen 56 Zeichen. Der Bequemlichkeit halber können wir alle Blauen Programme der Länge 1 in Band 1 unterbringen, Programme mit 2 Zeichen in Band 2 usw. Es braucht nicht betont werden, daß die ersten Bände völlig leer sein werden, während spätere Bände viele, viele Eintragungen haben werden (aber jeder Band nur eine endliche Anzahl). Das allererste Blaue Programm wäre:
    PROZEDURDEFINITION „A“ [B]:
    BLOCK 0: ANFANG
    BLOCK 0: ENDE
    Dieser eher alberne Fleischwolf gibt den Wert 0, was immer auch der Input sein möge. Er steht in Band 58, da er 58 Zeichen hat (wobei auch die nötigen Zwischenräume einschließlich derer, die aufeinanderfolgende Zeilen trennen, gezählt werden).
    Bald nach Band 58 werden die Bände äußerst dick, weil es so viele Millionen von Möglichkeiten gibt, Symbole zur Erzeugung von Blauen Programmen zu kombinieren. Das macht aber nichts, wir werden diesen unendlichen Katalog nicht ausdrucken. Uns interessiert lediglich, daß er im abstrakten Bereich wohldefiniert ist, und daß deshalb jedes Blaue BlooP-Programm eine einzige und definitive Indexzahl besitzt. Das ist die entscheidende Überlegung.
    Bezeichnen wir die von dem k -ten Blauen Programm errechnete Funktion wie folgt:
    Blauprogramm {Nr. k } [ N ]
    Hier ist k die Indexzahl des Programms, und N ist der einzige Input-Parameter. Zum Beispiel könnte Blaues Programm Nr. 12 einen doppelt so großen Wert als Output ergeben:
    Blauprogramm {Nr. 12} [ N ] = 2 × N
    Die Bedeutung der obigen Gleichung ist die, daß das auf der linken Seite genannte Programm den gleichen Wert ergibt, den auch ein Mensch aus dem gewöhnlichen algebraischen Ausdruck rechts errechnen würde. Ein weiteres Beispiel: vielleicht errechnet das 5000. Blaue Programm die dritte Potenz des Input-Parameters:
    Blauprogramm {Nr. 5000} [ N ] = N 3
Die Diagonalmethode
    Nun gut — und jetzt wenden wir den „Dreh“ an: Cantors Diagonalmethode. Wir werden diesen Katalog von Blauen Programmen nehmen und ihn zur Definition einer neuen Funktion mit einer Variablen — Blaudiag [ N ] — benutzen, von der sich herausstellen wird, daß sie sich nirgends auf der Liste befindet (weshalb ihr Name hier kursiv gesetzt wurde). Und doch wird Blaudiag offensichtlich eine wohldefinierte, errechenbare Funktion einer Variablen sein, und so müssen wir zum Schluß kommen, daß es Funktionen gibt, die einfach in BlooP nicht programmierbar sind.
    Hier die Definition von Blaudiag [ N ]:
    Gleichung 1) ... Blaudiag [ N ] = 1 + Blauprogramm {Nr. N } [ N ]
    Die anzuwendende Strategie lautet: Speise jeden Fleischwolf mit seiner eigenen Indexzahl; dann addiere 1 zum Output. Zur Illustration berechnen wir Blaudiag [12]. Wir haben gesehen, daß Blauprogramm {Nr. 12} die Funktion 2 N ist; deshalb muß Blaudiag [12] den Wert 1 + 2 × 12 oder 25 besitzen. Gleichermaßen hätte Blaudiag [5000] den Wert 125000000001, da das 1 mehr ist als die dritte Potenz von 5000. In ähnlicher Weise läßt sich Blaudiag für jedes gewünschte Argument finden.
    Das merkwürdige an Blaudiag [ N ] ist, daß es im Katalog der Blauen Programme nicht repräsentiert ist. Das kann es gar nicht, und zwar deshalb, weil es, um ein Blaues Programm zu sein, eine Indexzahl haben müßte — nehmen wir an, es wäre Blaues Programm Nr. X. Diese Annahme wird durch die folgende Formel ausgedrückt:
    Gleichung 2) ... Blaudiag [ N ] = Blauprogramm {Nr. X} [ N ]
    Zwischen den Gleichungen 1) und 2) besteht ein Widerspruch. Er wird erkennbar in dem Augenblick, in dem wir versuchen, den Wert von Blaudiag [ X ] zu berechnen, denn das können wir tun, indem wir in beiden Gleichungen N den Wert von X annehmen lassen. Wenn wir die Gleichung 1 substituieren, erhalten wir
    Blaudiag [ X ] = 1 + Blauprogramm {Nr. X } [ X ]
    Wenn wir aber statt dessen in Gleichung 2 substituieren, erhalten wir
    Blaudiag [ X ] = Blauprogramm {Nr. X } [ X ]
    Nun kann Blaudiag [ X ] nicht gleich einer Zahl und zugleich der Nachfolger dieser Zahl sein. Das aber behaupten diese beiden Gleichungen. Wir müssen also zurückgehen und einige Annahmen ausmerzen, auf denen der Widerspruch beruht. Der einzige mögliche Kandidat zur Ausmerzung ist die in Gleichung 2 ausgedrückte Annahme: daß die