BuK/IIm20/Vorlesung 6 Thomas

Wiki-Quelltext dieser Seite.

== Aufgabe 1 ==
Defnieren Sie je eine totale Funktion für den Vorgänger und die Halbierung einer natürlichen Zahl. Defnieren Sie außerdem eine Funktion mit $ D_f = \N \setminus \{1234, 7266281\} $.


Funktionsdefinition Vorgänger (total) :  
$f(n) =
\left \{
	\begin{array}{ll}
		n-1  & \mbox{, wenn n} > 0\\
                0 & \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.$

== Aufgabe 2 ==

Was liefert eigentlich haelt?(haelt?) bzw. $(haelt? haelt?)$?

$haelt?(f) =
\left \{
	\begin{array}{ll}
		wahr  & \mbox{, wenn haelt_fuer_n?(f , 0);}\\
                falsch & \mbox{, sonst.} \\
	\end{array}
\right.$

$haelt?$ als Funktion ($f$) einfügen ... 

$haelt?(haelt?) =
\left \{
	\begin{array}{ll}
		wahr  & \mbox{, wenn haelt_fuer_n?(haelt? , 0);}\\
                falsch & \mbox{, sonst.} \\
	\end{array}
\right.$

es folgt ein Aufruf von $haelt?(0)$ in der Funktion $haelt\_fuer\_n?(haelt? , 0)$.

Die Funktion $haelt?(f)$ erwartet eine Funktion und keine Natürliche Zahl, somit ist der Aufruf $haelt?(0)$ unzulässig. Es kommt zu einen Fehler.

== Aufgabe 3 ==

[[Bild:St52pybu_Buk_6_1.jpg]]

== Aufgabe 4 ==
Turing-Maschine berechnet Funktion - Verdopplungsmaschine

[[Bild:St52pybu_Buk_6_2.jpg]]

$
11, q0, 0
$

$
\$1, q1, 1
$

$
\$1\$, q1, 2
$

$
\$1\$\$, q2, 3
$

$
\$1\$1\$, q3, 4
$

$
\$1\$11, q4, 3
$

$
\$1\$11, q4, 3
$

$
\$1\$11, q4, 2
$

$
\$1\$11, q5, 1
$

$
\$1\$11, q5, 0
$

$
\$1\$11, q0, 1
$


$
\$\$\$11, q1, 2
$

$
\$\$\$11, q2, 3
$

$
\$\$\$11, q2, 4
$

$
\$\$\$11\$, q2, 5
$

$
\$\$\$111\$, q3, 6
$

$
\$\$\$1111, q4, 5
$

$
\$\$\$1111, q4, 4
$

$
\$\$\$1111, q4, 3
$

$
\$\$\$1111, q4, 2
$

$
\$\$\$1111, q4, 1
$

$
\$\$\$1111, q5, 1
$

$
\$\$\$1111, q0, 2
$

$
\$\$\$1111, q6, 3
$

== Aufgabe 5 ==