\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen,automaten}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 3},
  Thematik = {Berechen- und Entscheidbarkeit},
  Referenz = 66115-2017-F.T2-A3,
  RelativerPfad = Examen/66115/2017/03/Thema-2/Aufgabe-3.tex,
  ZitatSchluessel = examen:66115:2017:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Berechenbarkeit, Turing-Maschine},
  EinzelpruefungsNr = 66115,
  Jahr = 2017,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 3,
}

\begin{enumerate}

%%
% 1.
%%

\item Primitiv rekursive Funktionen\index{Berechenbarkeit}
\footcite{examen:66115:2017:03}

\begin{enumerate}

%%
% a)
%%

\item Zeigen Sie, dass die folgendermaßen definierte Funktion
if: $\mathbb{N} \times \mathbb{N} \times \mathbb{N}
\mathbb{N}$ primitiv rekursiv ist.

sonst

%%
% b)
%%

\item Wir nehmen eine primitiv rekursive Funktionp: NN an und definieren
g(n) als die Funktion, welche die größte Zahl i < n zurückliefert, für
die p(/) = 0 gilt. Falls kein solches i existiert, soll g(n) = 0 gelten:

a(n) = max ({i <n |p) = 0} U {0})

if (b, x, y) = ( falls b=0
\end{enumerate}

Zeigen Sie, dass g: N > N primitiv rekursiv ist. (Sie dürfen obige
Funktion if als primitiv rekursiv voraussetzen.)

%%
% 2.
%%

\item Sei \bAlphabet{a, b, c} und $L \subseteq \Sigma^*$ mit
\bAusdruck{a^i b^i c^i}{i \in N}.
\begin{enumerate}

%%
% a)
%%

\item Beschreiben Sie eine Turingmaschine, welche die Sprache Z
entscheidet. Eine textuelle Beschreibung der Konstruktionsidee ist
ausreichend.
\index{Turing-Maschine}

\begin{bAntwort}
\begin{center}
\begin{tikzpicture}[li turingmaschine]
  \node[state,initial] (q0) at (2.14cm,-2.57cm) {$q_0$};
  \node[state] (q1) at (5.14cm,-2.57cm) {$q_1$};
  \node[state] (q2) at (7.43cm,-2.57cm) {$q_2$};
  \node[state] (q3) at (9.86cm,-2.57cm) {$q_3$};
  \node[state] (q4) at (2.14cm,-4.71cm) {$q_4$};
  \node[state,accepting] (q5) at (5cm,-4.71cm) {$q_5$};

  \bTuringKante[above]{q0}{q1}{
    a, X, R;
  }

  \bTuringKante[above]{q0}{q4}{
    Y, Y, R;
  }

  \bTuringKante[above]{q1}{q2}{
    b, Y, R;
  }

  \bTuringKante[above,loop above]{q1}{q1}{
    a, a, R;
    Y, Y, R;
  }

  \bTuringKante[above]{q2}{q3}{
    c, Z, L;
  }

  \bTuringKante[above,loop above]{q2}{q2}{
    b, b, R;
    Z, Z, R;
  }

  \bTuringKante[above,loop above]{q3}{q3}{
    a, a, L;
    Y, Y, L;
    b, b, L;
    Z, Z, L;
  }

  \bTuringKante[above,bend left]{q3}{q0}{
    X, X, R;
  }

  \bTuringKante[above]{q4}{q5}{
    LEER, LEER, L;
  }

  \bTuringKante[above,loop below]{q4}{q4}{
    Y, Y, R;
    Z, Z, R;
  }
\end{tikzpicture}
\end{center}
\bFlaci{Apew1n7g9}
\bFussnoteUrl{https://scanftree.com/automata/turing-machine-for-a-to-power-n-b-to-power-n-c-to-power-n}
\end{bAntwort}

%%
% b)
%%

\item Geben Sie Zeit- und Speicherkomplexität (abhängig von der Länge
der Eingabe) Ihrer Turingmaschine an.

\begin{bAntwort}
\begin{description}
\item[Speicherkomplexität] $n$ (Das Eingabewort wird einmal überschrieben)
\item[Zeitkomplexität]

the turing machine time complexity is the number of transition execution will executed is call time complexity of the turing machine. first we start we main loop execution is (n/3)-1.
 transition(a,x,R) from state 1 to 2= 1.
transition (a,a,R) and (y,y,R) on state 2 is = (n/3)-1.
transition (b,y,R) from state 2 to 3=1.
on state 3 (b,b,R) and  (z,z,R)=(n/3)-1.
transition (c,z,L) from state 3 to 4=1.
on state 4 (y,y,L),(b,b,L),(z,z,L) and state 5 (a,a,L)= (n/3)-1.
transition (a,a,L) form state 4 to 5 =1.
transition (x,x,R) from 5 to1 =1
total(n+2)
following transition will executed
transition(a,x,R) from state 1 to 2= 1.
transition (y,y,R) on state 2 is = (n/3)-1.
transition (b,y,R) from state 2 to 3=1.
 transition (z,z,R) on state 3=(n/3)-1
transition (c,z,L) from state 3 to 4=1.
on state 4 (y,y,L) ,(z,z,L) and state  (n/3)-1.
transition (x,x,R) from state 54 to 6 =1
transition on state 6 (y,y,R),(z,z,R)= (n/3)
transition (d,d,R) from state 6 to 7 =1
total =(4n/3)+2
over alti time complexity (n+2)(n/3)-1+ (4n/3)+2
\bFussnoteUrl{https://www.youtube.com/watch?v=vwnz9e_Lrfo}
\end{description}
\end{bAntwort}
\end{enumerate}

%%
% 3.
%%

\item Sei \bAlphabet{0, 1}. Jedes $w \in \Sigma^*$ kodiert eine
Turingmaschine $M_w$. Die von  $M_w$ berechnete Funktion bezeichnen wir
mit $\varphi_w(x)$.

\begin{enumerate}

%%
% a)
%%

\item Warum ist
\bAusdruck
{w \in \Sigma^*}
{\exists x \colon \varphi_w(x) = xx} nicht entscheidbar?

%%
% b)
%%

\item Warum ist \bAusdruck
{w \in \Sigma^*}
{\exists x \colon w = xx} entscheidbar?

\end{enumerate}
\end{enumerate}
\end{document}