\documentclass{bschlangaul-aufgabe}
\bLadePakete{mathe}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Verständnis Berechenbarkeitstheorie},
  Thematik = {Verständnis Berechenbarkeitstheorie},
  Referenz = 66115-2016-F.T2-A2,
  RelativerPfad = Examen/66115/2016/03/Thema-2/Aufgabe-2.tex,
  ZitatSchluessel = examen:66115:2016:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Berechenbarkeit},
  EinzelpruefungsNr = 66115,
  Jahr = 2016,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 2,
}

Beantworten\index{Berechenbarkeit} \footcite{examen:66115:2016:03} Sie
kurz, präzise und mit Begründung folgende Fragen: (Die Begründungen
müssen keine formellen mathematischen Beweise sein)
\footcite[F2016T2A2 (Check-Up), Aufgabe 9]{theo:ab:4}

% Info_2021-06-11-2021-06-11_13.34.15

\begin{enumerate}

%%
% a)
%%

% 47min

\item Warum genügt es, sich auf Funktionen zu beschränken, die
natürliche Zahlen auf natürliche Zahlen abbilden, wenn man untersuchen
will, was heutige Computer im Prinzip berechnen können?

\begin{bAntwort}
Jede WHILE-berechenbare Funktion ist turing-berechenbar. Jede
turing-berechenbare Funktion ist WHILE-berechenbar. Jede
nichtdeterministische Turing-Maschine kann durch eine deterministische
Turing-Maschine simuliert werden.\footcite[Seite 24-28]{theo:fs:4}
\end{bAntwort}

%%
% b)
%%

\item Was besagt die Church-Turing-These? Könnte man sie beweisen oder
widerlegen?

\begin{bAntwort}
Die Church-Turing-These besagt, dass die Klasse der turing-berechen\-baren
Funktionen mit der Klasse der intuitiv berechenbaren Funktionen
übereinstimmt. Die These kann nicht bewiesen oder widerlegt werden, weil
es sich bei dem Begriff \emph{„intuitiv berechenbare Funktion“} um
keinen mathematisch exakt definitierten Begriff handelt. Würde man ihn
genau definierten, würde ein konkretes Berechnungsmodell festlegt
werden, was der Kernaussage dieses Begriffes widersprechen würde.
\footcite[Seite 308, These 6.1]{hoffmann}
\end{bAntwort}

%%
% c)
%%

% 50 min

\item Für reelle Zahlen, wie \zB $\pi$, lässt sich die
Dezimaldarstellung durch entsprechende Programme beliebig genau
approximieren. Gilt das für alle reellen Zahlen, \dh lässt sich für
jede reelle Zahl die Dezimaldarstellung mit entsprechenden Programmen
beliebig genau approximieren?

\begin{bAntwort}
Ja mit einer Berechnungsvorschrift, ja solange der speicherplatz reicht,
z. B. mittels Intervallschachtelung.
\end{bAntwort}

%%
% d)
%%

\item Was ist für die Berechnungskraft der wesentliche Unterschied
zwischen While-Berechenbarkeit und Loop-Berechenbarkeit.

\begin{bAntwort}
Alle LOOP-Programme sind mathematisch betrachtet totale Funktionen,
\dh sie terminieren immer. WHILE-Programme hingegen partiellen
Funktionen, die nicht für alle Eingabekombinationen terminieren.
\footcite[Seite 258-259]{hoffmann}
\end{bAntwort}

%%
% e)
%%

% 55min

\item Die Ackermannfunktion ist ein Beispiel einer totalen Funktion, die
While-berechenbar, aber nicht Loop-berechenbar ist. Sie verallgemeinert
die Idee, dass Multiplikation die wiederholte Addition ist,
Exponentiation die wiederholte Multiplikation, Hyperexponentiation die
wiederholte Exponentiation usw. Die Stufe dieser hyper-hyper ...
Exponentiation ist ein Parameter der Ackermannfunktion. Generieren Sie
aus dieser Idee ein Argument, das illustriert, warum die
Ackermannfunktion nicht Loop-berechenbar ist.

\begin{bAntwort}
Jedes LOOP-Programm benötigt zur Berechnung der Funktion $x \uparrow^n
y$ mindestens $n + 2$ Schleifen.

Gäbe es ein LOOP-Programm, das $ack(n,
m)$ tatsächlich für beliebige Werte von $n$ berechnet, so müsste dieses
--- im Widerspruch zum endlichen Aufbau eines Loop-Programms ---
unendlich viele Schleifenkonstrukte enthalten.

\bPseudoUeberschrift{Hyperexponentiation}

\begin{itemize}
\item $x \uparrow^{-1} y = x + y$
\item $x \uparrow^0 y = x \cdot y$
\item $x \uparrow^1 y = x^y$
\item $x \uparrow^2 y = x^{y^y}$

\end{itemize}
\footcite[Seite 258]{hoffmann}
\end{bAntwort}

%%
% f)
%%

% 59 min

\item Geben Sie ein Beispiel einer Menge an, die abzählbar, aber nicht
rekursiv aufzählbar ist, und begründen Sie es.

\begin{bAntwort}
\begin{itemize}
\item Die Menge der Primzahlen. Die Primzahl sind unendlich groß und
könnten abgezählt werden. Bei Primzahlen gibt es keine
Berechnungsvorschrift, die z. b. die 7. Primzahl berechnet.

\item Die Menge der Turningmaschine

\item Diagonalsprache

\item Das Komplement des Halteproblems. Die dem Halteproblem
zugrundeliegende Lösungsmenge ist rekursiv aufzählbar. Wäre das
Komplement des Halteproblems auch rekursiv aufzählbar, dann wäre das
Halteproblem entscheidbar, was es aber nicht ist.
\bFussnoteUrl{https://www.youtube.com/watch?v=om4ZTOeQuD0}
\end{itemize}
\end{bAntwort}

%%
% g)
%%

\item Wie ist der Zusammenhang zwischen rekursiv aufzählbar und
semi-entscheidbar?

\begin{bAntwort}
Die beiden Begriffe sind äquivalent.
\bFussnoteUrl{https://www.youtube.com/watch?v=om4ZTOeQuD0}
\end{bAntwort}

\end{enumerate}
\end{document}