Die Komplexitätsschranke: Wie komplex können wir etwas beweisen?
2025-04-22
Dieser Artikel untersucht die Grenzen der rechnerischen Komplexität. Mathematiker haben eine „Komplexitätsschranke“ entdeckt: Wir können nicht beweisen, dass die Komplexität einer bestimmten Bitfolge diese Schranke übersteigt. Überraschenderweise ist diese Schranke bemerkenswert niedrig, möglicherweise nur wenige Kilobyte. Der Artikel behandelt auch den Kritchman-Raz-Beweis von Gödels zweitem Unvollständigkeitssatz und die Möglichkeit, unberechenbare Funktionen in nicht-standardmäßigen Modellen der Arithmetik zu berechnen, was zu philosophischen Überlegungen zum Konzept der standardmäßigen natürlichen Zahlen führt.