Ubungsblatt 7 - Informatik 2

RHEINISCHWESTFÄLISCHE
TECHNISCHE
HOCHSCHULE
AACHEN
LEHRSTUHL FÜR INFORMATIK II
RWTH Aachen · D-52056 Aachen
http://www-i2.informatik.rwth-aachen.de/
2
Prof. Dr. Ir. J.-P. Katoen
C. Kern, S. Rieger, A. Skopalik
Berechenbarkeit und Komplexität WS 2008/09
– Übungsblatt 7 –
Abgabe bis zum 5.12.2008 um 12:00 (Sammelkasten Lehrstuhl Informatik I)
Besprechung der Lösungen in der Woche vom 8.-12.12.2008 in den Kleingruppenübungen
Aufgabe 3
(5 Punkte)
b) Wir zeigen zunächst, dass DLOOP = {i ∈ N|Pi verwirft i} nicht durch Loop-Programme entscheidbar
ist. Anschliessend zeigen wir, dass daraus folgt, dass ALOOP nicht durch Loop-Programme entschieden
werden kann.
Wir nehmen an, Pj sei das LOOP-Programm, das DLOOP entscheidet. Was macht Pj auf der Eingabe
j?
Falls Pj auf j verwirft, folgt aus der Definition von DLOOP , dass j ∈ DLOOP gilt. In dem Fall müsste
aber Pj auf j akzeptieren, wie aus der Definition von Pj folgt.
Falls Pj auf j akzeptiert, folgt aus der Definition von DLOOP , dass j 6∈ DLOOP gilt. In dem Fall müsste
aber Pj auf j verwerfen, wie aus der Definition von Pj folgt.
Annahme: ALOOP sei durch ein Loop-Programm PLOOP entscheidbar. Wir konstruieren nun ein LoopProgramm P , welches DLOOP entscheidet und PLOOP als Unterprogramm benutzt. Bei Eingabe j führe
PLOOP mit (j, j) aus und akzeptiere, genau dann, wenn PLOOP verwirft.
Partielle Korrektheit:
j ∈ DLOOP ⇒ Pj akzeptiert j nicht ⇒ (j, j) 6∈ ALOOP ⇒ PLOOP verwirft (j, j) ⇒ P akzeptiert j.
j∈
/ DLOOP ⇒ Pj akzeptiert j ⇒ (j, j) ∈ ALOOP ⇒ PLOOP akzeptiert (j, j) ⇒ P verwirft j.
Also kann DLOOP und damit auch ALOOP nicht von einem LOOP-Programm entschieden werden.

Download Report