BuK/IIm18/Vorlesung5

Wiki-Quelltext dieser Seite.

== Ü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.
[[Bild:Paul_Bachmann_PCP.png|center|thumb|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.