Vorlesung5
Inhaltsverzeichnis |
Übungsaufgabe 1
Definieren Sie je eine totale Funktion für den Vorgänger und die Halbierung einer natürlichen Zahl. Definieren Sie außerdem eine Funktion mit D_f = \N \backslash \{1234, 7266281\}.
Übungsaufgabe 2
Für K = ((001,0)(01,001),(01,101),(10,001)) gibt es eine Lösung. Die gesuchte Indexfolge heißt
(2~4~3~4~4~2~1~2~4~3~4~3~4~4~3~4~4~2~1~4~4~2~1~3~4~1~1~3~4~4~4~2~1~2~1~1~1~3~4~3~4~1~2~1~4~4~2~1~4~1~1~3~4~1~1~3~1~1~3~1~2~1~4~1~1~3)Überprüfen Sie die angegebene Lösung per Hand.
Übungsaufgabe 3
Entwickeln Sie eine Scheme-Prozedur (vorhandene ProgrammingWiki-Lösung verwenden), die bei Aufruf für eine gegebene Instanz eine Lösung des PCP �findet, falls eine solche existiert (und der Rechenaufwand im Rahmen bleibt).
Übungsaufgabe 4
Geben Sie Trichterbilder für den Einsatz einer TM als Akzeptor an:
1) für semi-entscheidbare Sprachen.
2) für entscheidbare Sprachen.
Übungsaufgabe 5
Definieren Sie die Begriffe Turing-aufzählbar und Turing-entscheidbar analog zur Turing-Berechenbarkeit.