BuK/IIm18/Vorlesung6

Wiki-Quelltext dieser Seite.

== Übungsaufgabe 1 ==
Eine TM soll überprüfen ob $w$ die Form $uu$ besitzt. Für $u$ gilt $a^ib^ic^i$

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