Für ein Alphabet [img]http://mokrates.de/cgi-bin/texstring?%5CSigma[/img] und

[img]http://mokrates.de/cgi-bin/texstring?%20x%20%20%5Cepsilon%20%20%5CSigma%5E%7B*%7D[/img] sei K(x) die Länge des kürzesten Programms (in einer beliebigen aber festen Programmiersprache), das x ausgibt. Zeigen SIe, dass K nicht berechenbar ist.

Bisherige Idee: Annahme durch Widerspruch. Anname K ist berechenbar. Nun nehme ich dieses Programm als Unterprogramm in einem weiteren Programm, mit dem ich dann die Annahme zum Widerspruch führen sollen könnte.
Aber irgendwie verläuft es da im Sand, hat wer ne Idee dazu?

ok google ist mein freund.
im prinzip wollen die den beweis haben das kolmogorov-komplexitaet nicht berechenbar ist; standardbeweis in
jeder literatur, uebungspunkte wieder mal ne woche gerettet, frohes neues an alle :)