Gib eine untere Schranke für die mittlere Kolmogorov Komplexität eines zufällig unter Gleichverteilung ausgewählten 0-1-Strings der Länge n an.
Wir wollen mittels Kolmogorov Komplexität beweisen, dass es unendlich viele Primzahlen gibt. Angenommen, es gäbe nur endlich viele Primzahlen, sagen wir p_1,p_2,...,p_k. Sei nun n eine genügend große Zahl, sodass die Kolmogorov Komplexität der Binärdarstellung von n nicht komprimierbar sei, also K(bin(n)) >= |bin(n)| = log n. Jede natürliche Zahl hat eine eindeutige Primzahlzerlegung, also n=p_1^{n_1}p_2^{n_2}...p_k^{n_k}. Indem wir nun die Zahlen n_1,n_2,...,n_k (geeignet als Bitstrings codiert) angeben, haben wir n eindeutig beschrieben, und n (bzw bin(n)) kann aus dieser Information eindeutig rekonstruiert werden.
Leite daraus eine obere Schranke für K(bin(n)) ab, die im Widerspruch zur obigen Wahl von n steht und somit beweist, dass es doch unendlich viele Primzahlen gibt.
Sei PI(n) die Anzahl der Primzahlen kleiner als n. Zeige mittels Kolmogorov Komplexität (ähnliche Überlegung wie in Aufgabe 10.2), dass PI(n) >= log n/log log n.
Bemerkung: Dieses (sehr schwache) Primzahltheorem lässt sich noch relativ leicht auf PI(n) >= n/(log n)^2 verbessern.
Bemerkung: Das klassische Primzahltheorem besagt, dass PI(n) sich asymptotisch verhält wie n/log n.