Was ist der Zweck der Interpretation von Elementen im Beweis der Reduktion von PCP auf das Gültigkeitsentscheidbarkeitsproblem der Prädikatenlogik?

7

Da sich meine Frage direkt auf einen Teil des Textes aus einem Buch aus dem Jahr 2004 bezieht, Logik in der Informatik: Modellierung und Argumentation über Systeme (2. Auflage) von Michael Huth und Mark Ryan , um den Kontext für die folgende Diskussion bereitzustellen, bin ich teilweise das Buch wörtlich zitieren:

Das Entscheidungsproblem der Gültigkeit in der Prädikatenlogik ist unentscheidbar: Es gibt kein Programm, das gegeben ist φentscheidet, ob .φ

Beweis: Wie bereits gesagt, geben wir vor, dass die Gültigkeit für die Prädikatenlogik entscheidbar ist, und lösen damit das (unlösbare) Post-Korrespondenzproblem. Bei einer Korrespondenzprobleminstanz : wir in der Lage sein, innerhalb eines endlichen Raums und einer begrenzten Zeit und für alle Instanzen einheitlich eine Formel der Prädikatenlogik zu konstruieren, so dass gilt, wenn die Korrespondenzprobleminstanz oben eine Lösung hat.C

s1s2...sk
t1t2...tk
φφC

Als Funktionssymbole wählen wir eine Konstante und zwei Funktionssymbole und für die jeweils ein Argument erforderlich ist. Wir denken an als leere Zeichenfolge oder Wort undef0f1ef0 und f1 stehen symbolisch für Verkettung mit 0 bzw. 1. Also wenn b1b2...bl ist eine binäre Bitfolge, die wir als Begriff codieren können fbl(fbl1...(fb2(fb1(e)))...). Beachten Sie, dass diese Codierung dieses Wort rückwärts buchstabiert. Um das Lesen dieser Formeln zu erleichtern, werden Begriffe wie abgekürztfbl(fbl1...(fb2(fb1(t)))...) durch fb1b2...bl(t).

Wir benötigen auch ein Prädikatsymbol Pdas erwartet zwei Argumente. Die beabsichtigte Bedeutung vonP(s,t) ist, dass es eine Folge von Indizes gibt (i1,i2,...,im) so dass s ist der Begriff, der darstellt si1si2...sim und t repräsentiert ti1ti2...tim. Somit,s Konstruiert eine Zeichenfolge mit derselben Indexfolge wie diese t;; nurs verwendet die si wohingegen t verwendet die ti.

Unser Satz φ hat die grobe Struktur φ1φ2φ3 wo wir setzen

φ1=defi=1kP(fsi(e),fti(e))

φ2=defv,wP(v,w)i=1kP(fsi(v),fti(w))

φ3=defzP(z,z)
.

Unser Anspruch ist φ gilt für das Post-Korrespondenzproblem C hat eine Lösung.

Zum Nachweis von PCP ⟹ Gültigkeit:

Nehmen wir umgekehrt an, dass das Post-Korrespondenzproblem C eine Lösung hat. [...] Wir gehen hier vor, indem wir endliche binäre Zeichenfolgen im Bereich der Werte interpretierenA des Modells M. Dies ist nicht unähnlich der Codierung eines Interpreters für eine Programmiersprache in einer anderen. Die Interpretation erfolgt durch eine Funktionsinterpretation , die induktiv in der Datenstruktur endlicher binärer Strings definiert ist:

interpret(ϵ)=defeM

interpret(s0)=deff0M(interpret(s))

interpret(s1)=deff1M(interpret(s))
.

[...] Verwenden von [interpret(b1b2...bl)=fblM(fbl1M(...(fb1M(eM)...)))] und die Tatsache, dass Mφ1, Wir schließen daraus (interpret(si),interpret(ti))PM zum i=1,2,...,k. [...] schon seitMφ2Das wissen wir für alle (s,t)PM wir haben das (interpret(ssi),interpret(tti))PM zum i=1,2,...,k. Verwenden Sie diese beiden Fakten, beginnend mit(s,t)=(si1,ti1)verwenden wir wiederholt die letztere Beobachtung, um zu erhalten

(2.9) (interpret(si1si2...sin),interpret(ti1ti2...tin))PM.

[...] Daher überprüft (2.9) zP(z,z) im M und somit Mφ3.

Um zu beweisen, dass die Gültigkeit der Prädikatenlogik unentscheidbar ist, habe ich nach dem Ansatz, den ich aus der Schule gelernt habe und der auf dem des Huth & Ryan-Buches (2. Auflage, Seite 135) basiert , bei der Konstruktion der Reduktion von PCP auf das Gültigkeitsproblem das "endliche binäre Zeichenketten" des Universums werden mit einer " Interpretationsfunktion " interpretiert , die binäre Zeichenketten in Kompositen von Funktionen des Modells codiert.

Dann zeigt es das unter Verwendung der Tatsache, dass der Vorgänger von φmuss gelten, damit es nicht trivial ist, können beide Unterformeln des Antezedens mit der genannten " Interpretationsfunktion " ausgedrückt werden . Daraus folgt, dass auch die Konsequenz gilt, da sie auch mit der Interpretationsfunktion ausgedrückt werden kann, die sich aus den vorherigen Ausdrücken mit interpret ergibt .

Meine Frage ist: Was ist der Zweck dieser " Interpretationsfunktion "? Warum können wir nicht einfach das zuvor entwickelte φ verwenden und das gleiche Ergebnis erzielen? Was bringt es uns, Interpret zu verwenden, um unsere Elemente auszudrücken?

Und was ist, wenn unser Universum willkürliche Elemente enthält? Was ist, wenn es sich nicht um binäre Zeichenfolgen handelt? Konstruieren wir nur eine Abbildung der beiden?

RexYuan
quelle
Willkommen auf der Seite! Bitte versuchen Sie, Ihre Frage eigenständiger zu gestalten. Wir können nicht wissen, was Sie mit Antezedenz von meinenφ wenn wir nicht wissen wer φist, also sollten Sie wahrscheinlich eine Beschreibung der Reduzierung hinzufügen. Sie sollten auch Ihre Quellen genau angeben (welches Buch), damit niemand raten muss. Ich habe dies im ersten Teil meiner Antwort behandelt, aber ich denke, es sollte auch in der Frage erscheinen.
Ariel

Antworten:

7

Beginnen wir mit dem, was genau Sie beweisen wollen.

Sie haben es mit einer Unterschrift zu tun σ welches aus einer Konstante besteht e, zwei Funktionssymbole f0,f1und ein binäres Prädikat P(s,t). Wir bezeichnen mitC die Menge aller "Ja" -Instanzen für das Post-Korrespondenzproblem, dh alle Sequenzen geordneter Paare von Binärzeichenfolgen (s1,t1),...,(sk,tk) so dass es Indizes gibt i1,...,in für einige nN die befriedigen si1...sin=ti1...tin ( steht für Verkettung).

Sie möchten das bei einer bestimmten Instanz zeigen c=(s1,t1),...,(sk,tk) dann zum Postkorrespondenzproblem

cC Wenn M ist ein Modell, das interpretiert σ, dann M φ(c)

Wo φ(c)=φ1(c)φ2(c)φ3(c), und

φ1(c)=i=1kP(fsi(e),fti(e)),

φ2(c)=v,wP(v,w)i=1kP(fsi(v),fti(w)),

φ3(c)=zP(z,z).

Oben eine binäre Zeichenfolge angegeben s=s1,...,sl, fs bezeichnet die Zusammensetzung fslfsl1...fs1. Dies ist die Reduktion von PCP auf die Gültigkeit in der Prädikatenlogik, die in "Logik in der Informatik" von Huth & Ryan beschrieben ist.

Wir denken an f0,f1 als Verkettung mit 0,1 entsprechend und von eals leere Zeichenfolge. In diesem Fall können wir uns vorstellenfs(e) als Darstellung der Zeichenfolge s in der Welt von M. Intuitiv,φ1,φ2 erzwinge das Prädikat P(v,w) zu halten wann (vielleicht auch in einigen anderen Fällen, aber es ist uns egal) v=fs(e),w=ft(e) (bedeutet, dass v,w sind die Interpretationen einiger endlicher Zeichenketten s,t in der Welt von M) und es gibt eine Folge von Indizes i1...in so dass s=si1...sin und t=ti1...tin. WennP(v,w) hat in der Tat diese Bedeutung (was passiert, wenn M befriedigt φ1φ2), dann cCzP(z,z).

Sie fragen nach dem Richtung des Beweises, also müssen Sie mit beliebigen Modellen umgehen, die interpretieren σ, wo die Welt Elemente haben kann, die nichts mit Strings zu tun haben (dies bezieht sich auf Ihre zweite Frage). Hier kommt die Interpretationsfunktion ins Spiel. Wir geben eine Entsprechung zwischen allen endlichen Strings und einer Teilmenge der Welt vonM, was angesichts der Art unserer Unterschrift ziemlich natürlich ist. Ein Fadens wird dem Element zugeordnet fs(e)Dies kann eine Zeichenfolge / Zahl / Tabelle oder alles sein, was Sie möchten.

Nun, wenn wir die Fähigkeit haben, an Elemente der Form zu denken fs(e) im AM (die Welt von M) als endliche Zeichenketten können wir weitermachen und das beweisen Implikation. WennM befriedigt φ1,φ2dann, wie wir erwähnt haben, P(v,w) gilt wann v=fs(e),w=ft(e) (Jetzt können wir uns vorstellen v,w as strings), and there exists a sequence of indices i1...in such that s=si1...sin and t=ti1...tin. Thus, if cC, and i1...in is a sequence of indices with s=si1...sin=ti1...tin=t, then P(fs(e),ft(e)) holds, and we have Mφ3, since s=t implies fs(e)=ft(e).

Ariel
quelle
Hello, Ariel! Thanks for answering! Sorry not getting back sooner. I wasn't expecting to be answered so promptly with such a nice answer! I'll revise my question to include more context (maybe by quoting the book)! Thanks!
RexYuan