Vorlesung5

Aus ProgrammingWiki
< BuK < IIm18

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\}.

Vorgängerfunktion:

$f(n) = \left \{ \begin{array}{ll} n-1 & \mbox{, wenn n} > 0\\

               1 & \mbox{, sonst.} \\

\end{array} \right.$


Halbierungsfunktion

$g(n) = \left \{ \begin{array}{ll} \frac{ n }{ 2} & \mbox{, wenn n gerade } \\

               \frac{ n+1 }{2}  & \mbox{, sonst.} \\

\end{array} \right.$


Funktion mit D_f = \N \backslash \{1234, 7266281\}:

$h(n) = \left \{ \begin{array}{ll} n & \mbox{, wenn }n \neq 1234 \mbox{ und } n \neq 7266281\\

               1 & \mbox{, sonst.} \\

\end{array} \right.$

Übungsaufgabe 2

Für K = ((001,0)(01,011),(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.

Paul_Bachmann_PCP.png
upright=6

Ü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.