\documentclass{bschlangaul-aufgabe}
\bLadePakete{mathe,syntax}
\begin{document}
\bAufgabenMetadaten{
  Titel = {WHILE-berechenbar},
  Thematik = {2 hoch x, ggT, if},
  Referenz = THEO.Berechenbarkeit.WHILE-berechenbar,
  RelativerPfad = Module/70_THEO/20_Berechenbarkeit/Aufgabe_WHILE-berechenbar.tex,
  ZitatSchluessel = theo:ab:4,
  ZitatBeschreibung = {Aufgabe 2},
  BearbeitungsStand = unbekannt,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {WHILE-berechenbar},
}

Bestimme jeweils, ob die angegebene Funktion WHILE-berechenbar ist:
\index{WHILE-berechenbar}
\footcite[Aufgabe 2]{theo:ab:4}

\begin{enumerate}

%%
% (a)
%%

\item $x \rightarrow 2^x$

\begin{bAntwort}
\begin{minted}{md}
erg = 1;
WHILE x != 0 DO
  erg = erg * 2;
  x = x - 1;
END;
return erg;
\end{minted}
\end{bAntwort}

%%
% (b)
%%

\item $\text{ggT}(n, m)$,

also der größte gemeinsame Teiler. Sie dürfen die (ganzzahligen)
Operationen $+$, $−$, $*$ und $/$ verwenden, wobei das Minus, wie
üblich, eingeschränkt ist.

\begin{bAntwort}
Es bietet sich an, zunächst die modulo Operation

\begin{minted}{md}
x_i := x_j % x_k
\end{minted}

durch folgendes WHILE-Programm zu definieren:

\begin{minted}{md}
x_n+1 := x_j / x_k;
x_n+2 := x_n+1 * x_k;
x_i := x_j - x_n+2;
\end{minted}

Wobei $x_{n+1}$ und $x_{n+1}$ im Rest des Programmes nicht verwendet
werden sollen. Mit der Modulo Operation kann man nun \zB einfach den
euklidischen Algorithmus verwenden (Eingabe seien $x_1$ und $x_2$,
Ausgabe ist $x_1$:

\begin{minted}{md}
WHILE x_2 != 0 DO
  x_3 := x_1 % x_2;
  x_1 := x_2 + 0;
  x_2 := x_3 + 0;
END
\end{minted}
\end{bAntwort}

%%
% (c)
%%

\item \begin{minted}{md}
if x_i != 0 then P_1 else P_2 fi
\end{minted}

mit der üblichen Semantik.
Als Nachweis kann jeweils ein WHILE-Programm angegeben werden.

\begin{bAntwort}
Sei $x_n$ die höchste in $P_1$ bzw. $P_2$ vorkommende Variable (o. E. $i
\leq n$).

\begin{minted}{md}
x_n+1 := x_i + 0;
x_n+2 := 1;
WHILE x_n+1 != 0 DO
  x_n+1 := 0;
  x_n+2 := 0;
  P_1;
END
WHILE x n+2 6 = 0 DO
  x_n+2 := 0;
  P_2;
END
\end{minted}
\end{bAntwort}

\end{enumerate}
\end{document}