Praktisches & Grundsätzliches zur Informatik

Logik, Entscheidbarkeit, Relativität

Zur Relativität logischer Entscheidbarkeit

Wenn Menschen der Meinung sind, eine gegebene Aussage A weder als wahr oder als falsch erkennen zu können, liegt das meist nur daran, dass sie sich nicht genügend informiert fühlen, eine sinnvolle Antwort zu geben. Man spricht hier von situationsbedingter Unentscheidbarkeit.

Wo aber Logiker von Unentscheidbarkeit sprechen, meinen sie damit prinzipielle Unentscheidbarkeit.

Sie liegt genau dann vor, wenn — gegeben eine formale Logik L und eine Aussage A — die Gleichung L(A) = UNDEF gilt, was genau dann der Fall ist, wenn sowohl L(A) = WAHR, als auch L(A) = FALSCH einen logischen Widerspruch zur Folge hätte.

Hier bezeichnet L(A) den Wahrheitswert, den die Logik L der Aussage A zuordnet (es ist dies stets einer der Werte WAHR, FALSCH oder UNDEF).

Kurt Gödel konnte beweisen, dass es zu jeder formalen Logik L, welche mindestens die Arithmetik der natürlichen Zahlen modellieren kann, immer Aussagen A gibt, für die L(A) weder WAHR noch FALSCH sein kann.

Dies schließt nicht aus, dass es andere Logiken gibt, die der Aussage A durchaus einen Wahrheitswert zuordnen können. Wir sehen also:

Nicht nur situationsbedingte, sondern auch prinzipielle Unentscheidbarkeit kann relativ sein.


Weit weniger bekannt ist, dass es Aussagen gibt, die
  • hinsichtlich jeder Logik aus Sicht einer Person unentscheidbar,
  • aus Sicht aller anderen Personen aber WAHR sein können.
Dies gilt z.B. für die Aussage

A: » Person S erkennt diese Aussage A als FALSCH oder UNDEF. «


Beweis:

    S(A) = WAHR müsste S(A) = FALSCH oder UNDEF bedeuten — ein Widerspruch.

    S(A) = FALSCH aber hätte S(A) = WAHR zur Folge — ebenfalls ein Widerspruch.

    Demnach kann nur S(A) = UNDEF sein, und das bedeutet P(A) = WAHR für jede von S verschiedene Person P.

Hiermit ist beweisen:

Selbst prinzipielle (d.h. naturgegebene) Unentscheidbarkeit kann aus Sicht unterschiedlicher Personen etwas leicht Unterschiedliches sein.



Note: Das Beispiel findet sich — etwas anders formuliert — in David Deutsch: The Fabric of Reality, 1997, p. 237.

Deutsch scheint Entdecker dieser wirklich erstaunlichen Relativität zu sein.

Sein Buch allerdings ist von durchaus gemischter Qualität. Ganz abgesehen davon, dass Deutsch in einigen Kapiteln eher wirres Zeug von sich gibt, wundert man sich vor allem darüber, dass er (in Kap. 2) die Ergebnisses des Doppelspaltexperiments über Hugh Everetts Viele-Welten-Theorie begründet und dann auf Seite 51 sogar behauptet: "As I have just said, we do not need deep theories to tell us that parallel universes exist — single-particle interference phenomena tell us that." Er übersieht dabei, dass sein auf Seite 44-45 gegebener Erklärungsversuch der Ergebnisse eines erweiterten Doppelspalt­experiments die Existenz der Parallelwelten ja schon voraussetzt hat, sie also  n i c h t  beweisen kann.

Mich persönlich würde interessieren, ob Deutsch recht hat mit seiner Behauptung, dass Quantencomputer Probleme lösen können, die selbst Turingmaschinen nicht zu lösen in der Lage sind (Quantencomputer würden dann ja einen völlig neuen Berechenbarkeitsbegriff definieren). Auf Seite 218 seines Buches behauptet Deutsch nämlich, das der 1989 durch Charles Bennet und Gilles Brasard konstruierte erste Quantencomputer nicht Turing-berechenbare Probleme gelöst hätte. Ob er sich da nicht irrt? [1] [Ja, er irrt sich]

Siehe auch eine Rezension seines Buches, die ein anderer kritischer Leser – leider anonym – auf Amazon hinterlegt hat.




stw6473AURAussage . Unentscheidbarkeit . RelativitätNews?

Mehr + B G E + S H A + More