H ist nicht entscheidbar Korollar 296 ✟ B ❃⑦ REC, A ❃⑦ RE ✟ B ❃⑦ RE. ▲ A ❇ B ✱ A ❃⑦ REC ▲ A❇B✱ Beweis Aus der Annahme, dass B entscheidbar (bzw. semi-entscheidbar) ist, folgt wegen A ❇ B, dass dies auch auf A zutrifft (Widerspruch). ❥ Bemerkung Wegen K ❇ H überträgt sich somit die Unentscheidbarkeit von K auf H. Korollar H ❃⑦ REC. 297 Das Halteproblem bei leerem Band Definition Das Halteproblem bei leerem Band ist die Sprache die DTM Mw H0 ➐w ❃ ➌0, 1➑ ❲ → hält bei Eingabe ε ❻ Satz χH x1 x2 x3 w1 w2 w3 0 0 1 1 1 1 0 1 0 ✝ ✝ ✝ ✝ H0 ist RE-vollständig. Beweis ▲ H0 ❃ RE folgt wegen H0 ❇ H ❃ RE mittels der Reduktionsfunktion w w #ε. ✭ χH 0 x1 ❼ ε➁ w1 w2 w3 0 0 1 ✝ ✝ ✆ ✆ ✆ ✆ ✟ 298 H0 ist RE-vollständig Beweis ▲ ▲ H0 ❃ RE folgt wegen H0 ❇ H ❃ RE mittels der Reduktionsfunktion w w #ε. ✭ Sei A ❃ RE und sei w die Kodierung einer DTM, die χ ˆA berechnet. Um A auf H0 zu reduzieren, transformieren wir x ❃ ➌0, 1➑ in die Kodierung wx einer DTM M, die zunächst ihre Eingabe durch x ersetzt und dann Mw ❼x ➁ simuliert. Dann gilt ❻ x ❃A ✡✟ wx ❃ H0 und somit A ❇ H0 mittels der Reduktionsfunktion x Korollar H0 ❃⑦ REC. ✭ wx . Der Satz von Rice 299 Frage ▲ ▲ Kann man einer beliebig vorgegebenen DTM ansehen, ob die von ihr berechnete Funktion eine gewisse Eigenschaft hat? Kann man beispielsweise entscheiden, ob eine gegebene DTM eine totale Funktion berechnet? Antwort Nein (es sei denn, die fragliche Eigenschaft ist trivial, d.h. keine oder jede DTM berechnet eine Funktion mit dieser Eigenschaft). 300 Der Satz von Rice Definition ▲ Zu einer Klasse ❋ von Funktionen definieren wir die Sprache L❋ ➍w ❃ ➌0, 1➑ ▲ ❻ ❚ die DTM Mw berechnet eine Funktion in ❋ ➒ . Die Eigenschaft ❋ heißt trivial, wenn L❋ ❣ oder L❋ ➌0, 1➑ ist. Der Satz von Rice besagt, dass L❋ nur für triviale Eigenschaften entscheidbar ist. Satz (Satz von Rice) Für jede nicht triviale Eigenschaft ❋ ist L❋ unentscheidbar. ❻ 301 Der Satz von Rice Beispiel ▲ Die Sprache L ➌w ❃ ➌0, 1➑ ❻ ❙ Mw ❼0n ➁ 0n ✔ 1 für alle n ❈ 0➑ ist unentscheidbar. ▲ Dies folgt aus dem Satz von Rice, da die Eigenschaft ❋ ➌f ❙ f ❼0 n ➁ 0 n ✔ 1 für alle n ❈ 0➑ nicht trivial und L L❋ ist. ▲ ❋ ist nicht trivial, da z.B. die berechenbare partielle Funktion f ❼x ➁ ➣ n ✔1 ➝ , ➝0 ➛ ➝ ➝ ↕ , ✁ x 0n für ein n ❈ 0 sonst in ❋ und die konstante Funktion g ❼x ➁ 0 nicht in ❋ enthalten ist. 302 Der Satz von Rice Satz (Satz von Rice) Für jede nicht triviale Eigenschaft ❋ ist die Sprache L❋ unentscheidbar. Beweis ▲ Die Idee besteht darin, H0 auf L❋ (oder auf L❋ ) zu reduzieren, indem wir für eine gegebene DTM Mw eine DTM Mw ➐ konstruieren mit w ❃ H0 ▲ ▲ ▲ ▲ ✔ Mw ➐ berechnet (k)eine Funktion in ❋ . Hierzu lassen wir Mw ➐ bei Eingabe x zunächst einmal die DTM Mw bei Eingabe ε simulieren. Falls w ➯ H0 ist, berechnet Mw ➐ also die überall undefinierte Funktion u mit u ❼x ➁ für alle x ❃ ➌0, 1, #➑ . ✁ ❻ Damit die Reduktion gelingt, müssen wir nur noch dafür sorgen, dass Mw ➐ im Fall w ❃ H0 eine Funktion f berechnet, die genau dann die Eigenschaft ❋ hat, wenn u sie nicht hat. Da ❋ nicht trivial ist, gibt es eine DTM M, die eine solche Funktion f berechnet. 303 Der Satz von Rice Beweis (Schluss) ▲ ▲ Da ❋ nicht trivial ist, gibt es eine DTM M, die eine solche Funktion f berechnet. Betrachte die Reduktionsfunktion h❼w ➁ w , wobei w die Kodierung einer DTM ist, die bei Eingabe x zunächst die DTM Mw ❼ε➁ simuliert und im Fall, dass Mw ❼ε➁ hält, mit der Simulation von M ❼x ➁ fortfährt. ➐ ▲ Dann ist h ✂ w w ❃ H0 w ➯ H0 ▲ ➐ ✭ w eine totale berechenbare Funktion und es gilt ✟ Mw ➐ berechnet f ✟ Mw ➐ berechnet u. ➐ Dies zeigt, dass h das Problem H0 auf L❋ (oder auf L❋ ) reduziert, und da H0 unentscheidbar ist, muss auch L❋ unentscheidbar sein. ❥ 304 Der Satz von Rice für Akzeptoren Der Satz von Rice gilt auch für Eigenschaften, die das Akzeptanzverhalten einer gegebenen Turingmaschine betreffen. Satz (Satz von Rice für Spracheigenschaften) Für eine beliebige Sprachklasse ❙ sei L❙ ➌w ❃ ➌0, 1➑ ❻ ❙ L❼Mw ➁ ❃ ❙ ➑. Dann ist L❙ unentscheidbar, außer wenn L❙ ❃ ➌❣, ➌0, 1➑ Beweis Siehe Übungen. ❻ ➑ ist. 305 Das Postsche Korrespondenzproblem (PCP) Definition ▲ ▲ Sei Σ ein beliebiges Alphabet mit # ➯ Σ. Das Postsche Korrespondenzproblem über Σ (kurz PCPΣ ) ist: gegeben: k Paare ❼x1 , y1 ➁, . . . , ❼xk , yk ➁ von Wörtern in Σ . gefragt: Gibt es eine Folge α ❼i1 , . . . , in ➁, n ❈ 1, von Indizes ij ❃ ➌1, . . . , k ➑ mit xi1 . . . xin yi1 . . . yin ? ❻ ▲ ▲ Das modifizierte PCP über Σ (kurz MPCPΣ ) fragt nach einer Lösung α ❼i1 , . . . , in ➁ mit i1 1. Wir notieren eine PCP-Instanz meist in Form einer Matrix kodieren sie durch das Wort x1 #y1 # . . . #xk #yk . x ...x ❽y1 ...yk ➂ 1 k und Beispiel a ab caa ➂ Die Instanz I ❽xy11 xy22 xy33 ➂ ❽ aca bc aa besitzt wegen x1 x3 x2 x3 acaaabcaa y1 y3 y2 y3 acaaabcaa die PCP-Lösung α ❼1, 3, 2, 3➁, die auch eine MPCP-Lösung ist. ❘ 306 Das Postsche Korrespondenzproblem Lemma Für jedes Alphabet Σ gilt PCPΣ ❇ PCP➌a,b ➑ . Beweis ▲ Sei Σ ➌a1 , . . . , am ➑. Für ein Zeichen ai ❃ Σ sei c ❼ai ➁ ab i 1 und für ein Wort w w1 . . . wn ❃ Σ mit wi ❃ Σ sei c ❼w ➁ c ❼w1 ➁ . . . c ❼wn ➁. ✏ ❻ ▲ Dann folgt PCPΣ ❇ PCP➌a,b ➑ mittels der Reduktionsfunktion f ✂ x1 . . . xk ➄ y1 . . . yk ❿ ✭ ❿cc ❼❼xy1➁➁ .. .. .. cc ❼❼xyk ➁➁➄. 1 k Beispiel Sei Σ ➌0, 1, 2➑. Dann ist c ❼0➁ a, c ❼1➁ ab und c ❼2➁ abb. Somit ist 0 01 200 a aab abbaa f❿ ➄ ❿ ➄. 020 12 00 aabba ababb aa ❥ 307 Das Postsche Korrespondenzproblem Im Folgenden lassen wir im Fall Σ ➌a, b ➑ den Index weg und schreiben einfach PCP (bzw. MPCP). Satz MPCP ❇ PCP. Beweis ▲ Wir zeigen MPCP ❇ PCPΣ für Σ ➌a, b, ❵, ❙, ❡➑. ▲ Für ein Wort w w1 . . . wn sei w w w w ❵w1 ❙ . . . ❙wn ❙ ❵w1 ❙ . . . ❙wn ❙w1 ❙ . . . ❙wn w1 ❙ . . . ❙wn ❙ 308 Beweis von MPCP ❇ PCP ▲ ▲ Für ein Wort w w1 . . . wn sei w w w ❵❙w1 ❙ . . . ❙wn ❙ w1 ❙ . . . ❙wn ❙ ❵❙w1 ❙ . . . ❙wn ❙w1 ❙ . . . ❙wn Wir reduzieren MPCP mittels folgender Funktion f auf PCPΣ : f ▲ w ✂ x1 . . . xk ➄ y1 . . . yk ❿ ✭ ➆➈ x1 x1 . . . xk ❡➇ y1 y1 . . . yk ❙❡ ➉ Dabei nehmen wir an, dass ❼xi , yi ➁ ① ❼ε, ε➁ ist, da wir diese Paare im Fall i ❆ 1 einfach weglassen und im Fall i 1 f ❼I ➁ ❽aa➂ setzen können. Beispiel f ✂ ➀ aa b bab bb ➅ ✭ ➀ ❵❙a❙a❙ a❙a❙ b ❙ b ❙a❙b ❙ b ❙b ❙ ❡ ➅ 309 Beweis von MPCP ❇ PCP ▲ ▲ Für ein Wort w w1 . . . wn sei w w w ❵❙w1 ❙ . . . ❙wn ❙ w1 ❙ . . . ❙wn ❙ ❵❙w1 ❙ . . . ❙wn ❙w1 ❙ . . . ❙wn Wir reduzieren MPCP mittels folgender Funktion f auf PCPΣ : f ▲ w ✂ x1 . . . xk ➄ y1 . . . yk ❿ ✭ ➆➈ x1 x1 . . . xk ❡➇ y1 y1 . . . yk ❙❡ ➉ Da jede MPCP-Lösung α ❼1, i2 , . . . , in ➁ für I auf eine PCP-Lösung α ❼1, i2 ✔ 1, . . . , in ✔ 1, k ✔ 2➁ für f ❼I ➁ führt, folgt ➐ I ❃ MPCP ✟ f ❼I ➁ ❃ PCPΣ. 310 Beweis von MPCP ❇ PCP ▲ Wir reduzieren MPCP mittels folgender Funktion f auf PCPΣ : f ▲ ✂ x1 . . . xk ➄ y1 . . . yk ❿ ▲ ▲ x1 . . . xk ❡➇ y1 y1 . . . yk ❙❡ ➉ Für die umgekehrte Implikation sei α ❼i1 , . . . , in ➁ eine PCP-Lösung für ➐ f ❼I ➁ ▲ ✭ ➆➈ x1 ➆ x1 x1 . . . xk ❡➇ ➈ y1 y1 . . . yk ❙❡ ➉ . Dann muss i1 1 und in k ✔ 2 sein, da das Lösungswort mit ❵ beginnen und mit ❡ enden muss (und f ❼I ➁ nicht das Paar ❼ε, ε➁ enthält). Wählen wir α von minimaler Länge, so ist ij ❃ ➌2, . . . , k ✔ 1➑ für j 2, . . . , n ✏ 1. ➐ Dann ist aber α ❼i1 , i2 ✏ 1, . . . , in ✏ 1 ✏ 1➁ eine MPCP-Lösung für I. ❥ Das Postsche Korrespondenzproblem 311 Satz PCP ist RE-vollständig und damit unentscheidbar. Beweis. ▲ ▲ Es ist leicht zu sehen, dass PCP ❃ RE ist. Um zu zeigen, dass PCP RE-hart ist, sei A eine beliebige Sprache in RE und sei G ❼V , Σ, P, S ➁ eine Typ-0 Grammatik für A. ▲ Wir zeigen A ❇ MPCPΓ für Γ V ▲ Wegen MPCPΓ ❇ PCP folgt hieraus A ❇ PCP. ✽ Σ ✽ ➌❵, ❙, ❡➑. Beweisidee für die Reduktion A ❇ MPCPΓ : ...xk ➂, Transformiere eine Eingabe w ❃ Σ in eine Instanz f ❼w ➁ ❽yx11 ...y k ❻ so dass α ❼i1 , . . . , in ➁ genau dann eine MPCP-Lösung für f ❼w ➁ ist, wenn das zugehörige Lösungswort xi1 . . . xin yi1 . . . yin eine Ableitung S α0 ✆ αm w von w kodiert. ✟ ✟ 312 Das Postsche Korrespondenzproblem Beweis von A ❇ MPCPΓ ▲ Wir bilden f ❼w ➁ aus folgenden Wortpaaren: ❼ ❵ , ❵ ❙ S ➁, für jede Regel l r in P: ❼l, r ➁, für alle a ❃ V ✽ Σ ✽ ➌❙➑: ❼a, a➁, sowie das Paar ❼w ❙ ❡, ❡➁ „Startpaar“ „Ableitungspaare“ „Kopierpaare“ „Abschlusspaar“ ▲ Nun lässt sich leicht aus einer Ableitung S α0 in G eine MPCP-Lösung mit dem Lösungswort ✟ ✟ αm w von w ✆ ❵ ❙ α0 ❙ α1 ❙ . . . ❙ αm ❙ ❡ angeben. ▲ Umgekehrt lässt sich aus jeder MPCP-Lösung auch eine Ableitung von w in G gewinnen, womit w ❃ L ❼M ➁ gezeigt ist. ✔ f ❼w ➁ ❃ MPCPΓ ❥
© Copyright 2024 ExpyDoc
