Unentscheidbarkeit von SAT(FO)
-
Hallo zusammen,
irgendwie wurmt mich der Begriff der Entscheidbarkeit. Der Satz von Church und Turing besagt, dass SAT(FO) unentscheidbar ist. In SAT(FO) befinden sich alle prädikatenlogischen Formeln, die erfüllbar sind.
Doch was heißt jetzt unentscheidbar? Ich dachte, dass ein Problem entscheidbar ist, wenn es eine Turingmaschine sowohl für das Problem selbst, als auch für sein Komplement gibt.
SAT(FO) stelle ich mir wie eine große Menge vor. Wie hab ich mir hier die Unentscheidbarkeit vorzustellen?
Vielen Dank für eure Hilfe
LG, freakC++
-
freakC++ schrieb:
Ich dachte, dass ein Problem entscheidbar ist, wenn es eine Turingmaschine sowohl für das Problem selbst, als auch für sein Komplement gibt.
Es genügt auch eine einzige Turing-Maschine, solange sie das Problem entscheidet, d.h. "ja" oder "nein" zurückgibt.
Bei Teilmengen ist Entscheidbarkeit analog definiert: Eine Teilmenge A der natürlichen Zahlen heißt entscheidbar genau dann, wenn es eine Turingmaschine gibt, die auf Eingabe n entscheidet ob n in A ist oder nicht.
Formeln sind nur lange Bitstrings, also im Prinzip auch natürliche Zahlen.
-
Das hört sich für mich aber eher nach Erfüllbarkeit an. Das ist doch ein Unterschied. Der Satz von Post sagt doch:
Eine Sprache L ist genau dann entscheidbar, wenn sowohl L als auch ihr Komplement semi-entscheidbar, also rekursiv-aufzählbar == es gibt eine Turingmaschine, sind.
-
Wo studierst du, wenn man so direkt fragen darf? (Mir kommen deine Fragen ein wenig bekannt vor)
-
freakC++ schrieb:
Das hört sich für mich aber eher nach Erfüllbarkeit an.
Nein, das ist die Definition von Entscheidbarkeit. Erfüllbarkeit macht für eine formale Sprache keinen Sinn.
Der Satz von Post sagt doch:
Eine Sprache L ist genau dann entscheidbar, wenn sowohl L als auch ihr Komplement semi-entscheidbar, also rekursiv-aufzählbar == es gibt eine Turingmaschine, sind.
Dein Satz ist nicht vollständig. Es gibt eine Turingmaschine, die was genau macht? Eine Sprache L heißt semi-entscheidbar, wenn es eine Turingmaschine gibt, die für alle Wörter aus L und für kein Wort, das nicht in L ist, "ja" ausgibt. Die Sprache heißt entscheidbar, wenn es eine Turingmaschine gibt, die dabei immer terminiert, d.h. bei jedem Wort, das nicht in L ist, "nein" ausgibt.
-
freakC++ schrieb:
SAT(FO) stelle ich mir wie eine große Menge vor. Wie hab ich mir hier die Unentscheidbarkeit vorzustellen?
Du kannst nicht für jede belibige prädikatenlogische Formel mit Gewissheit sagen (entscheiden), ob sie erfüllbar ist oder nicht. Also: Du kannst im Allgemeinen nicht bestimmen, ob eine gegebene Formel in der Menge aller erfüllbaren Formeln liegt oder nicht (im speziellen kannst Du das natürlich sehr oft entscheiden). In der Sprache der Turingmaschinen: Es existiert keine Maschine, die dir diese Entscheidung (ausgabe "ja" oder "nein") bei beliebiger Eingabe einer PL-Formel liefert.
freakC++ schrieb:
Das hört sich für mich aber eher nach Erfüllbarkeit an.
Nein Du betrachtest die Menge der erfüllbaren Formeln und willst für eine gegeben Formel wissen, ob sie enthalten ist. Das ist das Entscheidungsproblem. Die Betonung liegt auf dem Enthaltensein der Menge, nicht auf der Erfüllbarkeit der Formeln. Du stolperst Deinen Fragen im Forum nach zu urteilen sehr oft über sprachliche Schlampereien. Genau lesen Du musst
-
Hallo zusammen,
vielen Dank für eure Antworten. Das bedeutet, doch eigentlich, dass alle Aussagen über prädikatenlogische Formelmengen nicht erfüllbar sind.
Außerdem frage ich mich, ob aus Entscheidbarkeit rekursive Aufzählbarkeit folgt. Eigentlich doch schon, denn wir hatten ja gesagt, dass Erfüllbarkeit das Stoppen der Turingmaschine sowohl auf dem Problem selbst, als auch auf dem Negat impliziert. Rekursive Aufzählbarkeit (Semientscheidbarkeit (Dieser Name deutet auch darauf hin
)) besagt, dass es das Problem durch eine Turingmaschine gelöst werden kann (siehe Beitrag von Michael E.))Vielen Dank
LG, freakC++
-
freakC++ schrieb:
vielen Dank für eure Antworten. Das bedeutet, doch eigentlich, dass alle Aussagen über prädikatenlogische Formelmengen nicht erfüllbar sind.
Nochmal: Was heißt "erfüllbar"? Für welche Strukturen hast du das Wort "erfüllbar" definiert?
Außerdem frage ich mich, ob aus Entscheidbarkeit rekursive Aufzählbarkeit folgt.
Ja.
Rekursive Aufzählbarkeit [...] besagt, dass es das Problem durch eine Turingmaschine gelöst werden kann
Du bist sprachlich zu ungenau. Was heißt denn "lösen"? Wenn du dich an die übliche Fachsprache hälst, tust du dich viel leichter mit solchen Überlegungen.
-
Das bedeutet, doch eigentlich, dass alle Aussagen über prädikatenlogische Formelmengen nicht erfüllbar sind.
Nein.