{3,56,6,23,78,...} und {2, 4,6,8,10,...}

lauten. Wie können wir beurteilen, wie zufällig diese Folgen sind? Wir hätten gern eine Antwort, die nicht auf unserem subjektiven Eindruck beruht, sondern etwas von dem verkörpert, was unser Geist uns über das Vorhandensein oder Fehlen von Ordnung verrät. Wir fragen, wie lang das kürzeste Computerprogramm ist, das diese Folgen erzeugt. Die in Computerbits gemessene Länge dieses kürzesten Programms wird die Komplexität der Folge genannt. Wenn eine Folge zufällig ist und keine besondere Regel zur Erzeugung einer Zahl aus einer anderen enthält (wie in unserem ersten Beispiel), kann das kürzeste Programm nicht kürzer sein als die Liste der Folge selbst. Wenn die Folge jedoch geordnet ist, kann das geforderte Programm viel kürzer sein als die gegebene unendlich lange Folge. Im zweiten unserer Beispiele gibt das Programm nur die geraden Zahlen an: {PRINT2N, N = l, 2,3,...}.

Eine Folge heißt zufällig, wenn ihre Komplexität gleich der Länge der Folge ist. In diesem Fall erfordert sie zu ihrer Beschreibung die gesamte Liste. Wenn irgend zwei verschieden lange Zufallsfolgen gegeben sind, wird die längere Folge als die komplexere angesehen. Wenn man sehr viele Zahlenfolgen, etwa Telefonnummern, betrachtet, findet man, daß sie meist eine ziemlich hohe Komplexität haben und sehr selten eine niedrige.

Unter Verwendung dieses Begriffs der Komplexität stelle man sich nun vor, man gäbe einem Computer, dessen Programme alle Symbole und Operationen der Arithmetik enthalten, die folgende Anweisung:

Drucke eine Folge, von deren Komplexität man beweisen kann, daß sie die Komplexität dieses Programms übertrifft.

Der Computer kann darauf nicht reagieren. Jede von ihm erzeugte Folge muß nach Definition eine Komplexität haben, die kleiner ist als seine eigene Komplexität. Ein Computer kann nur eine Zufallsfolge erzeugen, die weniger komplex ist als sein eigenes Programm. Wir sind jetzt in der Lage, diese Schwierigkeit zu untersuchen, um zu zeigen, daß es unentscheidbare Aussagen geben muß. Man wähle einfach eine Zufallsfolge, die zum Beispiel R heißt, deren Komplexität die des Computersystems übertrifft. Eine Frage wie «Ist R eine Zufallsfolge?» ist für das Computersystem unentscheidbar. Die Komplexität der Aussagen «R ist zufällig» und «R ist nicht zufällig», ist in jedem Fall zu groß, als daß sie vom Computersystem übersetzt werden könnte. Keine kann bewiesen oder widerlegt werden. Gödels Satz ist damit bewiesen. - (bar)