Fsk loesung blatt 11 PDF

Preview

Summary

FSK Lösungen zum Blatt 11 der Ludwig-Maximilians-Universität München...

Description

Prof. Dr. David Sabel Stephan Barth Gregor Kleen

Ludwig-Maximilians-Universit¨at M¨ unchen Institut f¨ur Informatik 22. Juni 2021

¨ bung zur Vorlesung L¨ osungsvorschlag zur 11. U

Formale Sprachen und Komplexit¨at (0 Punkte)

FSK11-1 Primitiv rekursive Pr¨ adikate

Primitiv rekursive Funktionen, die auf {0, 1} abbilden, k¨onnen auch als Pr¨ adikate aufgefasst werden. Wir betrachten in dieser Aufgabe nur einstellige Pr¨adikate p, wobei p(x) = 0 bedeutet, dass x die Eigenschaft p nicht besitzt, und p(x) = 1 bedeutet, dass x die Eigenschaft p besitzt. a) Zeigen Sie, dass die Funktion iszero ein primitiv rekursives Pr¨adikat ist. ( 0 f¨ur x > 0 iszero(x1 ) = 1 f¨ur x = 0

¨ LOSUNGSVORSCHLAG: Dass iszero auf {0,1} abbildet, ist an der Fallunterscheidung bereits zu sehen. Daher m¨ ussen wir nur noch zeigen, dass iszero primitiv rekursiv ist. Das kann man tun, indem man iszero wie folgt im primitiv rekursiven Schema angibt: ( 1 f¨ ur x1 = 0 iszero(x1 ) = 0 sonst

Dies entspricht dem Schema, denn es ist gleich ( g() iszero(x1 ) = h(iszero(x1 − 1), x1 − 1)

mit g() = 1 und h(y1 , y2 ) = 0 (konstante Funktionen)

f¨ur x1 = 0 sonst

b) Zeigen Sie, dass die Funktion even ein primitiv rekursives Pr¨adikat ist. ( 1 f¨ ur x1 gerade even(x1 ) = 0 f¨ ur x1 ungerade

¨ LOSUNGSVORSCHLAG: Auch hier gen¨ugt es, even im primitiv rekursiven Schema anzugeben: ( 1 f¨ ur x1 = 0 even(x1 ) = iszero (even (x1 − 1)) sonst

Die verwendeten Funktionen sind g() = 1 (konstante Funktion) und h(y1 , y2 ) = iszero(π12 (y1 , y2 )) (Komposition). Diese sind ebenfalls wieder in das primitiv rekursive Schema einzusetzen.

c) Zeigen Sie, dass die Funktion ifnotzero primitiv rekursiv ist. ( x2 falls x1 > 0 ifnotzero(x1 , x2 , x3 ) = x3 sonst

¨ LOSUNGSVORSCHLAG: Mit g(y1 , y2 ) = π22(y1 , y2 ), h(y1 , y2 , y3 , y4 ) = π 43 (y1 , y2 , y3 , y4 ) im primitiv rekursiven Schema erh¨alt man ifnotzero(x1 , x2 , x3 )

d) Zeigen Sie, dass die Funktion ifthenelse primitiv rekursiv ist, unter der Annahme, dass p(x) ein primitiv rekursives Pr¨adikat ist. ( x2 falls p(x1 ) ifthenelse(x1 , x2 , x3 ) = x3 sonst

¨ ifnotzero(p(x1 ), x2 , x3 ) LOSUNGSVORSCHLAG:

e) Zeigen Sie, dass, gegeben zwei primitiv rekursive Pr¨adikate p und q, auch die Konjunktion p ∧ q primitiv rekursiv ist. ¨ LOSUNGSVORSCHLAG: Mit Multiplikation oder zwei ifthenelse . Wir zeigen es hier sogar f¨ur beliebig-stellige Pr¨adikate: (p ∧ q)(x1 , . . . , xk ) = ifthenelse(p(x1 , . . . , xk ), ifthenelse(q (x1 , . . . , xk ), 1, 0), 0) 0,1 sind dabei die konstanten Funktionen mit k Parametern. Da wir in b) die Negation gemacht haben, und {¬, ∧} funktional vollst¨andig ist, k¨onnen wir damit beliebige logische Verkn¨upfungen herstellen.

FSK11-2 µ-Rekursion a) Berechnen Sie (µg) f¨ur i) g(x) = 7 ¨ LOSUNGSVORSCHLAG: µg ist u ¨berall undefiniert ii) g(x) = x ¨ LOSUNGSVORSCHLAG: (µg)(x) = 0 iii) g(x) = x + 1 ¨ LOSUNGSVORSCHLAG: µg ist u ¨berall undefiniert iv) g(x) =



0 if x ist Primzahl 1 sonst

¨ LOSUNGSVORSCHLAG: (µg)(x) = 2

(2 Punkte)

  0 x v) g(x1 , x2 ) =  1 undefiniert

falls x1 > x2 falls x1 < x2 sonst

¨ LOSUNGSVORSCHLAG:  0 (µg)(x2 ) = undefiniert

falls x2 > 0 sonst

Begr¨ undung: • Wenn x2 > 0, ist das kleinste x1 , sodass g(x1 , x2 ) = 0 ist, bereits f¨ur x1 = 0 erf¨ ullt. • Wenn x2 = 0, dann ist bereits g(0, 0) undefiniert, daher ist (µg )(x2 ) in diesem Fall undefiniert. vi) g(x1 , x2 ) = |x2 − x1 3 |, wobei − hier die unmodifizierte Subtraktion ist ¨ LOSUNGSVORSCHLAG: (µg)(x2 ) =

b) Betrachten Sie die Funktion ( k f (x1 ) = undefiniert



n undefiniert

if ∃n ∈ N.n3 = x2 sonst

falls k! = x1 , mit k ∈ N>0 sonst

Zeigen Sie, dass f µ-rekursiv ist. Geben Sie daf¨ur eine primitiv rekursive Funktion g an und zeigen Sie, dass (µg) = f . ¨ LOSUNGSVORSCHLAG: Die Multiplikation mul : N2 → N ist bereits als primitiv rekursiv bekannt. Damit l¨ asst sich die Fakult¨atsfunktion fak : N → N mit fak (x1 ) = x1 ! primitiv rekursiv ausdr¨ ucken:

fak (x1 ) =

( 1

h(fak (x1 − 1), x1 − 1)

wenn x1 = 0 sonst

h(x1 , x2 ) = mul (x1 , succ(x2 )) Wir definieren eine primitiv rekursive Hilfsfunktion g : N2 → N analog zu FSK112a)vi):

( 1 wenn x1 = 0 g(x1 , x2 ) = |x2 − fak (x1 )| sonst Es ist dann: (µg)(x2 ) =

( k

undefiniert

falls k! = x1 , mit k ∈ N>0 sonst

FSK11-3 Entscheidbarkeit oder Unentscheidbarkeit

(2 Punkte)

a) Die Funktion bin : N → {0, 1}∗ berechnet die Bin¨ardarstellung einer Zahl. Zeigen Sie, dass die Sprache   w, x ∈ {0, 1}∗ , die TM Mw berechnet bei Eingabe x = bin(42) R := w#x die Ausgabe bin(4711) unentscheidbar ist, indem Sie das allgemeine Halteproblem H auf R reduzieren (d.h. H ≤ R zeigen). ¨ LOSUNGSVORSCHLAG: Es sei:

( wM ′ #bin(42) f (x′ ) = x′

falls x′ = w#x sonst

Hierbei sei M ′ die TM, die: • ungeachtet der Eingabe (insbesondere also bei Eingabe bin (42)), x auf das Band schreibt, • die Turingmaschine Mw ausf¨uhrt (sie also auf der Eingabe x simuliert) und • bin(4711) auf das Band schreibt Die Funktion f ist total und berechnbar. Es gilt: g.d.w. g.d.w. g.d.w.

w#x ∈ H Mw h¨alt f¨ ur Eingabe x M ′ berechnet bei Eingabe bin(42) die Ausgabe bin (4711) wM ′ #bin(42) ∈ R

Damit folgt H ≤ R. Da H unentscheidbar ist, ist auch R unentscheidbar.

b) Sei DoubleDouble :=



w1 #w2 #u#v

die TM Mw1 h¨alt bei Eingabe u und die TM Mw2 h¨alt nicht bei Eingabe v



.

Zeigen Sie die Unentscheidbarkeit der Sprache DoubleDouble zweimal : i) durch eine Reduktion des Halteproblems bei leerer Eingabe auf DoubleDouble (d.h. Sie m¨ussen H0 ≤ DoubleDouble zeigen). ii) durch eine Reduktion des Komplements des Halteproblems bei leerer Eingabe auf DoubleDouble (d.h. Sie m¨ussen H0 ≤ DoubleDouble zeigen.) ¨ LOSUNGSVORSCHLAG: Sei MΩ eine (feste) TM, die ihre Eingabe ignoriert und nie h¨alt (z.B. MΩ = ({z0 }, Σ, Σ ∪ {}, δ, z0 , , ∅) mit δ (z0 , a) = (z0 , a, N ) f¨ur alle a ∈ Σ ∪ {}). Sei Mstop eine (feste TM), die ihre Eingabe ignoriert und stets h¨alt (z.B. Mstop = ({z0 }, Σ, Σ∪{}, δ, z0 , , {z0 }) mit δ(z0 , a) = (z0 , a, N ) f¨ur alle a ∈ Σ∪{}). Seien wΩ und wstop die TM-Beschreibungen (G¨odel-Nummern) von MΩ und Mstop . Sei nun f1 (w) = w#wΩ ## und f2 (w) = wstop #w##. Beide Funktionen sind total (da f¨ur jedes w definiert) und berechenbar. Die beiden verlangten Reduktionen sind: i) Es gilt: w ∈ H0 g.d.w. Mw h¨alt bei leerer Eingabe g.d.w. Mw h¨alt bei leerer Eingabe und MΩ h¨alt nicht bei leerer Eingabe g.d.w. w#wΩ ## ∈ DoubleDouble Damit folgt H0 ≤ DoubleDouble. Da H0 unentscheidbar ist, ist auch DoubleDouble unentscheidbar. ii) Es gilt: w ∈ H0 g.d.w. Mw h¨alt nicht bei leerer Eingabe g.d.w. Mw h¨alt nicht bei leerer Eingabe und Mstop h¨alt bei leerer Eingabe g.d.w. wstop #w## ∈ DoubleDouble Damit folgt H0 ≤ DoubleDouble. Da H0 unentscheidbar ist, ist auch DoubleDouble unentscheidbar.

c) Sei Double :=



w#u#v

die TM Mw h¨alt bei Eingabe u und alt nicht bei Eingabe v die TM Mw h¨



.

Zeigen Sie die Unentscheidbarkeit der Sprache Double, indem Sie DoubleDouble ≤ Double zeigen.

¨ LOSUNGSVORSCHLAG: Sei MΩ eine (feste) TM, die ihre Eingabe ignoriert und nie h¨alt (z.B. MΩ = ({z0 }, Σ, Σ ∪ {}, δ, z0 , , ∅) mit δ (z0 , a) = (z0 , a, N ) f¨ur alle a ∈ Σ ∪ {}). Sei wΩ die TM-Beschreibung (G¨odel-Nummer) von MΩ . Sei

( wM ′ #u#v f (x) = wΩ ##

falls x = w1 #w2 #u#v mit u 6= v sonst

Hierbei sei M ′ die TM, die: • pr¨ uft ob die Eingabe identisch ist mit u oder mit v • Mw1 ausf¨uhrt, falls die Eingabe identisch ist mit u und ansonsten Mw2 ausf¨ uhrt f ist total und berechenbar (es ist einfach eine Turingmaschine anzugeben, die ihre Eingabe auf Identit¨ at mit einem festen Wort pr¨uft und, je nach Ergebnis, auf zwei unterschiedliche Arten weitermachen kann). Es gilt: w1 #w2 #u#v ∈ DoubleDouble g.d.w. Mw1 h¨ alt bei Eingabe u und Mw2 h¨alt nicht bei Eingabe v g.d.w. M ′ h¨ alt bei Eingabe u und h¨alt nicht bei Eingabe v g.d.w. wM ′ #u#v ∈ Double Damit folgt DoubleDouble ≤ Double. Da DoubleDouble unentscheidbar ist, ist auch Double unentscheidbar. d) Welche der folgenden Fragestellungen zu einer Turingmaschine T = (Z, {a, b}, Γ, δ, z0 , , E) sind entscheidbar? Beweisen Sie ihre Antworten. Hinweis: Der Satz von Rice ist bei einigen dieser Fragen n¨utzlich ¨ LOSUNGSVORSCHLAG: Wiederholung: Satz von Rice: Sei R die Klasse aller Turingberechenbaren Funktionen. Sei S eine beliebige Teilmenge, sodass ∅ ⊂ S ⊂ R. Dann ist die Sprache C(S) = {w | die von Mw berechnete Funktion liegt in S} unentscheidbar.

i) T h¨alt bei jeder Eingabe der L¨ange |Z|2 .

¨ LOSUNGSVORSCHLAG: Das Problem ist unentscheidbar. Es gibt zwar nur endlich viele Eingaben der korrekten L¨ange, die Fragestellung ist jedoch f¨ur jede dieser Eingaben jeweils das spezielle Halteproblem. ii) T h¨ alt bei jeder Eingabe nach h¨ochstens |Z|2 Schritten. ¨ LOSUNGSVORSCHLAG: Das Problem ist f¨ ur jede Eingabe entscheidbar, indem man |Z |2 Schritte der Turingmaschine simuliert und anschließend pr¨uft, ob T angehalten hat oder nicht. Da die TM in den ersten |Z|2 Schritten auch h¨ochstens einen so langen Anfang des Wortes einlesen kann, ist es ausreichend alle W¨orter von dieser Anfangsl¨ange zu testen. Damit sind es nur endlich viele W¨orter und das Problem ist entscheidbar. iii) Wenn abaa ∈ L(T ), dann auch baabababbba ∈ L(T ). ¨ Folgt mit dem Satz von Rice und LOSUNGSVORSCHLAG: S = {f ∈ R | f (abaa) definiert ⇒ f (baabababbba) definiert} iv) Wenn es ein Wort w ∈ L(T ) gibt, dann gibt es auch ein Wort u, welches das Teilwort bab enth¨alt mit u ∈ L(T ). ¨ Folgt mit dem Satz von Rice und LOSUNGSVORSCHLAG: S = {f ∈ R | ∃w : f (w) definiert ⇒ ∃u, u′ ∈ {a, b}∗ : f (ubabu′ ) definiert }...