Allgemein

Erstmal hat du recht: Kolmogorov Komplexität ist wohl der gebräuchlichere Begriff. Weiterhin hast du recht: Der Artikel ist schlecht, und ich hatte wohl ein paar Dinge falsch verstanden. Ich hatte unter http://www.cwi.nl/~paulv/papers/020608isb.pdf nachgeschaut. -- Schewek

Gut, dann verschieb ich ihn erstmal und schau mal nach, ob ich bessere Infos finde... --Coma 19:43, 6. Jan 2003 (CET)

Hab nur eine sehr theoretische Abhandlung gefunden, die wohl auch vorkenntnisse erfordert. und ich hab auch keine Lust und Zeit selbst zu lesen... --Coma 20:07, 6. Jan 2003 (CET)

Dann werde ich mich nochmal schlaumachen, und morgen einen neuen Versuch machen. -- Schewek

Wenn ich es richtig verstanden habe, geht es um eine Beschreibungskomplexität. Eine Bitfolge läßt sich oft kürzer darstellen. Beispielsweise kann man 1000 Nullen auch durch die Zahl 1000 (in Binärform) ersetzen, was dann nur 10 Bit benötigt. Natürlich muss man dazu noch sagen, wie die neue Folge zu interpretieren ist, was durch ein Berechnungsprogramm geschehen kann, welches dann die ursprüngliche Folge wieder herstellt. Das braucht dann auch Speicher, aber für verschiedene Sprachen nur konstant viel zusätzlichen Speicher. (Ein Programm kann immer als Zahl kodiert werden). Die Zahl muss dann also auch immer noch mit angegeben werden. In der Sprache der beliebig langen Folgen von Nullen läßt sich ein Wort der Sprache also durch die Angabe der Anzahl von Nullen angeben. Zur Interpretation der Zahl benötigt man dann noch das Programm oder besser die Programmnummer, die aber für jedes Wort der Sprache konstant ist. Die Sprache der konstanten Folgen von Nullen besitzt dann logarithmische Komplexität, weil die Länge der Worte logarithmisch kodiert werden können, wobei noch die additven Kontante (für das Programm) dazukommt, welche aber nicht ins Gewicht fällt. Wenn das jemand so bestätigen oder präzisieren könnte, kann man da schon fast einen Artikel draus machen. --Coma 20:21, 6. Jan 2003 (CET)