omplexität   Nehmen wir an, wir hätten zwei Zahlenlisten vor uns, deren erste Einträge

{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)

Komplexität (2)  Jeder, der lacht - vom Stammesangehörigen in Guinea bis zur Professorenrunde in Oxford -, lacht aufgrund einer äußerst komplexen Körperreaktion, an der das Gehirn, die Gesichtsmuskeln, der Kehlkopf, das Zwerchfell und das ganze Atmungssystem beteiligt sind und bei der Brustmuskulatur, Unterleib, Hals und Rücken in Bewegung geraten. Es ist nicht einfach so, daß der Mensch das einzige Lebewesen ist, das biologisch mit einem Sinn für Humor ausgestattet zu sein scheint. Kin völlig humorloser Mensch, der unter keinen Umständen die Komik unseres Daseins begreifen kann, wird den meisten Beobachtern nicht nur reduziert, sondern auch unmenschlich erscheinen. - David B. Morris, Geschichte des Schmerzes. Frankfurt am Main 1996 (zuerst 1991)
 
 

Problem System Schwierigkeit

 

Oberbegriffe
zurück 

.. im Thesaurus ...

weiter im Text 
Unterbegriffe

 

Verwandte Begriffe
UnübersichtlichkeitVerwicklung

 Einfachheit

Synonyme
Kompliziert

Antonym