Lösung 6 - ita.inf.ethz.ch

Theoretische Informatik
Prof. Dr. Juraj Hromkovič
Prof. Dr. Emo Welzl
Departement Informatik
Lösungsvorschläge – Blatt 6
Zürich, 7. November 2014
Lösung zu Aufgabe 17
(a) Es gilt
(Linfinite ){ = {w ∈ {0, 1}∗ | w 6= Kod(M 0 ) für alle TM M 0 }
∪ {Kod(M ) | es gibt eine Eingabe x, so dass M auf x hält} .
Wir beschreiben im Folgenden eine nichtdeterministische Turingmaschine N mit
L(N ) = (Linfinite ){ . Es gibt also für jedes Wort aus w ∈ (Linfinite ){ eine endliche,
akzeptierende Berechnung von N auf w. Die NTM N überprüft für eine Eingabe w
zunächst, ob w = Kod(M ) für irgendeine TM M . Falls nicht, dann akzeptiert N die
Eingabe w. Falls w = Kod(M ) gilt für eine TM M , dann wählt N nichtdeterministisch
ein Wort x über dem Eingabealphabet von M und simuliert M deterministisch auf x.
Falls M auf dem Wort x hält, dann akzeptiert N ihre Eingabe w. Falls M auf x
unendlich lange rechnet, dann ist auch die Berechnung von N auf w unendlich.
Offenbar akzeptiert N alle Wörter, die nicht die Kodierung einer Turingmaschine sind.
Falls die Eingabe w die Kodierung einer TM M ist, dann ist w ∈ (Linfinite ){ genau dann,
wenn es ein Wort x gibt, so dass M auf x hält. Also gibt es dann eine akzeptierende
Berechnung von N auf w, in der N genau dieses Wort x nichtdeterministisch wählt.
Falls w ∈ Linfinite gilt, dann gibt es keine akzeptierende Berechnung von N auf w.
Also ist N eine NTM, die (Linfinite ){ akzeptiert, damit gilt (Linfinite ){ ∈ LRE .
(b) Wir zeigen LH,λ ≤EE (Linfinite ){ . Hierfür konstruieren wir eine TM A, die jede beliebige
Eingabe w für LH,λ in eine Eingabe A(w) für (Linfinite ){ umwandelt, so dass
w ∈ LH,λ ⇐⇒ A(w) ∈ (Linfinite ){ .
Die TM A testet zunächst, ob w = Kod(M ) gilt für irgendeine TM M . Falls nicht,
konstruiert A die Kodierung einer TM M1 , die auf keinem Wort hält.
Falls w = Kod(M ), dann konstruiert A die Kodierung einer TM NM , die wie folgt
arbeitet: NM ignoriert ihre eigene Eingabe und simuliert M auf λ.
1
Wir zeigen nun, dass w ∈ LH,λ ⇐⇒ A(w) ∈ (Linfinite ){ gilt.
Sei zunächst w ∈
/ LH,λ . Falls w nicht die Kodierung einer TM ist, dann ist A(w) = M1 ,
also A(w) ∈ Linfinite und damit A(w) ∈
/ (Linfinite ){ . Falls w = Kod(M ) für eine TM M ,
dann hält M nicht auf λ. Damit hält NM auf keiner Eingabe, also ist A(w) ∈
/ (Linfinite ){ .
Sei nun w ∈ LH,λ . Dann gilt w = Kod(M ) für eine TM M , die auf der Eingabe λ hält.
Damit hält NM auf jeder Eingabe, weil NM auf jeder Eingabe identisch arbeitet und
M auf λ simuliert. Also gilt A(w) = Kod(NM ) ∈ (Linfinite ){ .
(c) Wir zeigen zunächst die folgende Hilfsaussage, die bereits in der Vorlesung verwendet
wurde, aber nicht im Buch bewiesen ist:
Sei L eine Sprache über einem Alphabet Σ. Falls L ∈ LRE und L{ ∈ LRE ,
dann gilt auch L ∈ LR .
Um diese Aussage zu beweisen, konstruieren wir aus zwei Turingmaschinen M und
Mc , die L und L{ akzeptieren, eine neue Turingmaschine A, die L entscheidet. Die
Maschine A simuliert für eine Eingabe w ∈ Σ∗ einfach parallel die beiden Maschinen
M und Mc auf w. Falls w ∈ L, dann akzeptiert die Maschine M nach endlicher
Zeit das Wort w und A akzeptiert ebenfalls. Falls w ∈
/ L, dann akzeptiert Mc nach
endlicher Zeit das Wort w und A verwirft die Eingabe. In beiden Fällen gibt A also
nach endlich vielen Schritten die korrekte Antwort.
Wir können diese Hilfsaussage jetzt einfach verwenden, um Linfinite ∈
/ LRE zu zeigen.
Wir führen einen indirekten Beweis: Angenommen Linfinite ∈ LRE . Nach Aufgabenteil
(a) ist auch (Linfinite ){ ∈ LRE . Mit der Hilfsaussage folgt damit, dass (Linfinite ){ ∈ LR ,
im Widerspruch zu Aufgabenteil (b). Also ist die Annahme falsch und Linfinite ∈
/ LRE .
Lösung zu Aufgabe 18
(a) Um zu beweisen, dass (LU,λ ){ nicht rekursiv aufzählbar ist, zeigen wir, dass LU,λ ∈
/ LR
und LU,λ ∈ LRE gelten. Daraus folgt mit der Hilfsaussage aus Aufgabe 17 (c) sofort
die Behauptung.
Die Sprache LU,λ ist ein semantisch nichttriviales Entscheidungsproblem, denn sie
ist offenbar nicht leer, enthält nicht die Kodierungen aller Turingmaschinen und für
zwei beliebige Turingmaschinen A und B, die die gleiche Sprache akzeptieren, gilt
Kod(A) ∈ LU,λ ⇐⇒ Kod(B) ∈ LU,λ . Nach dem Satz von Rice folgt somit, dass
LU,λ ∈
/ LR .
Um zu zeigen, dass LU,λ rekursiv aufzählbar ist, konstruieren wir eine Turingmaschine
A, die LU,λ akzeptiert. Die Maschine A überprüft zunächst, ob ihre Eingabe eine
gültige Form hat, also Kod(M ) ist für eine Turingmaschine M . Falls nicht, dann
verwirft A ihre Eingabe. Sonst simuliert A die Arbeit von M auf λ. Falls M auf λ
im akzeptierenden Zustand hält, dann akzeptiert auch A. Falls M das leere Wort
verwirft, dann verwirft auch A. Falls M auf λ unendlich lange läuft, dann läuft auch
A unendlich lange. Somit akzeptiert A die Sprache LU,λ .
2
(b) Um zu zeigen, dass Lall nicht rekursiv ist, geben wir eine Reduktion von der universellen
Sprache LU an, d. h. wir zeigen LU ≤R Lall . Wir nehmen also an, wir hätten eine
Turingmaschine A für Lall zur Verfügung und konstruieren hieraus eine Turingmaschine
B für LU .
Die Maschine B prüft zunächst, ob ihre Eingabe die Form Kod(M )#w hat für eine
Turingmaschine M . Falls nicht, dann verwirft sie die Eingabe. Sonst konstruiert sie
eine Turingmaschine NM , die ihre eigene Eingabe ignoriert und M auf w simuliert. Die
Kodierung von NM dient dann als Eingabe für A. Die Turingmaschine B übernimmt
nun die Ausgabe der Maschine A auf der Eingabe Kod(NM ).
Falls Kod(M )#w ∈ LU , dann akzeptiert M das Wort w. Damit akzeptiert NM jede
Eingabe, weil NM auf jeder Eingabe identisch arbeitet und M auf w simuliert. Somit
ist Kod(NM ) ∈ Lall und A akzeptiert Kod(NM ). Damit akzeptiert auch B die Eingabe
Kod(M )#w.
Falls Kod(M )#w ∈
/ LU , dann akzeptiert M das Wort w nicht. Damit akzeptiert NM
keine Eingabe, also ist Kod(NM ) ∈
/ Lall und A verwirft Kod(NM ). Damit verwirft
auch B die Eingabe.
Lösung zu Aufgabe 19
Sei L eine unendliche Sprache. Mit Hilfe der Diagonalisierungsmethode können wir eine
Teilmenge L0 von L definieren, die nicht rekursiv aufzählbar ist. Sei Mi die i-te Turingmaschine in kanonischer Ordnung. Dann definieren wir eine Diagonalsprache relativ zu L wie
folgt:
Ldiag,L = {w ∈ {0, 1}∗ | w ist das i-te Wort in L für ein i ∈
und Mi akzeptiert wi nicht} .
N
Offenbar gilt Ldiag,L ⊆ L.
Angenommen, es sei Ldiag,L ∈ LRE . Dann ist Ldiag,L = L(M ) für eine TM M . Weil M
eine der Turingmaschinen in der Aufzählung aller Turingmaschinen sein muss, existiert ein
i ∈ , so dass M = Mi . Die Sprache Ldiag,L kann aber nicht gleich L(Mi ) sein, weil die
folgende Äquivalenz gilt:
wi ∈ Ldiag,L ⇐⇒ wi ∈
/ L(Mi ) .
N
Dies ist ein Widerspruch, also gilt Ldiag,L ∈
/ LRE .
3

Download Report