Hey Liated,

Darf ich nochmals nachhaken? Die C-S läuft (auch) mit
echten Zufallszahlen-Sequenzen:
Wie sieht in Diesem Fall aus? Ist dann die
C-S im gödelschen Sinne unvolllständig?

Wie gesagt ich wäre vorsichtig mit dem Begriff "echt". "Umgebungsrauschen" hat zwar eine hohe Entropie und ist zu bevorzugen, aber es kann dennoch determiniert sein (selbst wenn es durch QM Effekte kommt). Das spielt aber keine Rolle, denn der zentrale Aspekt ist einfach die Berechenbarkeit oder die Vorhersagbarkeit. Solange es nicht um Verschlüsselung geht, kannst auch einen PRNG nehmen. Der wäre für einen Hacker, dann prinzipiell eher knackbar, aber für die C-S halte ich das für irrelevant. Rauschen am Audioeingang des PC ist eben praktisch unmöglich zu "hacken" (weil der Hacker die Ursachen nicht zurückverfolgen kann) als eine Zufallszahl die über ein PRNG Algorithmus zustande kommt (der eben eher reverse-engineer bar ist).

Mit Gödel hat das aber wirklich gar nix zu tun. Bei Gödel geht es um Ableitbarkeit aus Axiomen. Es geht darum ob man einen mathematischen Satz mit den vorhandenen Axiomen prinzipiell beweisen kann. Also etwa ob man den "Satz des Pythagoras" aus der euklidschen Axiomen beweisen kann (das geht). Gödel zeigt nun, dass bei einer Axiomatik basierend auf klassischer Logik die wenigstens die natürlichen Zahlen enthält die Annahme der Vollständigkeit zu widersprüchen führt.

Wie kann man dann beweisen, dass nicht ALLE Sätze ableitbar sind, wenn man nicht jeden Satz kennt?! Er nutz dazu einen coolen Trick (nur mal schematisch dargestellt).

Wenn man jedes Mathematische Symbol einer Zahl zuordnet. Also etwa so

001: +
002: -
003: *
004: /
005: =
.
.
.
116: 1
117: 2
118: 3
.
.
.
246: A
247: B
248: C
.
.
.
.
479: ²
480: ³
.
.
.

Etc

Dann heißt dass die Menge aller natürlichen Zahlen die Menge aller Sätze ist.

Nach obigem Schema wäre also die Zahl...:

246479001247479005248479

...der Satz des Pythagoras:

A²+B²=C²

Natürlich kommen dabei auch sinnlose Sätze vor (nicht wohldefiniert sagt der Mathematiker). Also etwa a+)=1. Aber das macht nix.

Man hat auf diese Weise durch die Natürlichen Zahlen jeden sinnigen und unsinnigen Satz. Somit hätte man also Vollständigkeit.

Jetzt lässt sich aber auf diese weise ein Satz konstruieren der sagt (Vorsicht schematisch):

Satz X => Satz X ist falsch.

Wenn satz x wahr ist, ist er also falsch und wenn er falsch ist, ist wahr. Das ist quasi das Lügnerparadoxon.

Das bedeutet die Annahme der Vollständigkeit führt zu einem eindeutigen Widerspruch. Eine Axiomatik die Widersprüche erzeugt ist aber nutzlos, weil ex falso quodlibet.

Daher muss man sich damit abfinden, dass die klassische Logik mit einer Axiomatik mit natürlichen Zahlen eben nicht vollständig ist (der Gödelsche Beweis führt nur wegen dieser Annahme zum widerspruch). Das heißt nicht, dass die Mathematik jetzt zwangsläufig widerspruchsfrei ist. Es kann sein, dass morgen ein Mathematiker einen Widerspruch findet und man die Axiomatik ändern muss. Es heißt nur, dass die Axiomatik der natürlichen Zahlen auf jeden Fall widersprüchlich wäre, wenn sie vollständig wäre und somit unvollständig sein muss.

Dass das ganze nicht nur theoretischer Spinnerei ist und auch für Sätze gelten kann die nicht selbstbezüglich sind, zeigt die Kontinuumshypothese.

Wie du siehst, hat das mit Berechenbarkeit nix zu tun sondern geht um Beweisbarkeit.

Übrigens war Gödel ein Bekannter Einsteins (beide waren in Princeton) und war eine Genie von vergleichbarer Größenordnung. Wobei ich Einsteins Denkmuster interessanter finde. Der hat was verspieltes/verträumtes in seinem Denken. Als Kind war er ein Tagträumer und träumte auf Mondwellen zu reiten. Später dachte er über das reiten auf Lichtwellen nach und schuf mit seiner Tagträumerei ein neues Physik Paradigma. Diese kindliche verspielte Kreativität zu erhalten war in seinem Denken von großer Bedeutung.

Einstein kennt fast jeder, Gödel kaum einer.

Grüße
melethron

--
„It’s the Second Law of Thermodynamics: Sooner or later everything turns to shit.“ - Woody Allen