Vorlesung6

Übungsaufgabe 1

Eine TM soll überprüfen ob w die Form uu besitzt. Für u gilt a^ib^ic^i, bei Korrektheit von w soll u auf dem Band hinterlassen werden.

Übungsaufgabe 2

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