close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Blatt 4 - Lehrstuhl Informatik 1

EinbettenHerunterladen
Lehrstuhl für Informatik 7
Prof. Dr. Wolfgang Thomas
Kamal Al-Bawani, Sascha Geulen,
Oliver Göbel, Benjamin Ries, Lisa Wagner
WS 2014/15
05.11.2014
Übung zur Vorlesung
Berechenbarkeit und Komplexität
Blatt 4
Aufgabe 4.1
Gegeben sei die Turingmaschine M = ({q0 , q1 , q¯}, {0, 1}, {0, 1, B}, B, q0 , q¯, δ) mit δ wie
folgt:
0
1
B
q0 (q0 , 1, R) (q0 , 0, R) (q1 , B, L)
q1 (q1 , 0, L) (q1 , 1, L) (¯
q , B, R)
Berechnen Sie das Kodewort M von M wie in der Vorlesung definiert.
Aufgabe 4.2
(a) Beweisen Sie die folgende Aussage: Wenn ein Aufzähler E existiert, der alle Wörter einer unendlichen Sprache L in kanonischer Reihenfolge ausgibt, dann ist L
entscheidbar.
(b) Zeigen Sie, dass die Sprache
D = { M | M hält auf Eingabe M }
aufzählbar ist.
Aufgabe 4.3
(4 Punkte)
Welche der folgenden Sprachen sind entscheidbar? Begründen Sie jeweils Ihre Antwort.
(a) H≤16 = { M w | M hält auf Eingabe w und zwar nach höchstens 16 Schritten}
(b) H≥16 = { M w | M hält auf Eingabe w und zwar nach mindestens 16 Schritten}
(c) H42 = { M w | M hält auf Eingabe w und besucht dabei genau 42 Bandpositionen}
Abgabe bis Mittwoch, den 12.11.2014 um 14.00 Uhr
im Sammelkasten am Lehrstuhl für Informatik 1.
Document
Kategorie
Sport
Seitenansichten
10
Dateigröße
143 KB
Tags
1/--Seiten
melden