uni/ws2019/ipi/uebungen/ipi1.tex

\documentclass{lecture}

\begin{document}

\begin{aufgabe}[MIU ist abzählbar]
\end{aufgabe}

Jedem Knoten des Baums wird eine natürliche Zahl zugeordnet, indem ganz links
in der ersten Reihe gestartet wird, und dann durchgezählt wird. Falls
ein Wort bereits zugeordnet wurde, wird diesem Wort wieder die selbe Zahl
zugeordnet.

Dadurch erhält jedes Wort im MIU System eine eindeutige natürliche Zahl und,
da es unendlich viele Worte gibt, jede natürliche Zahl auch ein Wort.

\begin{aufgabe}[Das PG-System]
    Es sei $A$ = $\{-, p, g\}$ ein Alphabet. Die Worte des PG-Systems
    haben die Gestalt:
    \begin{center}
        -\ldots-p-\ldots-g-\ldots-
    \end{center}
    Die Anzahl der $-$ Zeichen \textit{nach} dem $g$ ist die Summe der $-$
    Zeichen \textit{vor} dem $p$ \textit{und} zwischen $p$ und $g$.
\end{aufgabe}

Regelsatz:

Im folgenden sind $x_1$ und $x_2$ eine beliebige Anzahl von $-$.
\begin{enumerate}
    \item $- x_1 p x_2 g x_1 x_2 -$
    \item $x_1$p$ - x_2 g x_1 x_2 -$
\end{enumerate}

\begin{aufgabe}[Addition mit Turingmaschine]
\end{aufgabe}

Programm:

\begin{table}[htpb]
    \centering
    \begin{tabular}{|c|c|c|c|c|}
        \hline
        \textbf{Zustand} &  \textbf{Eingabe} &  \textbf{Operation} & \textbf{Folgezustand} & \textbf{Bemerkung} \\ \hline
        1 & 1 & 0,rechts & 2 &  Anfangszustand \\ \hline
        2 & 1 & 1,rechts & 2 &  \\
        2 & 0 & 1,rechts & 3 &  \\ \hline
        3 & 1 & 1,rechts & 3 &  \\
        3 & 0 & 0,links  & 4 &  \\ \hline
        4 & 1 & 0,links  & 5 &  \\ \hline
        5 & 1 & 1,links  & 5 &  \\
        5 & 0 & 1,rechts & 6 &  \\ \hline
        6 & 1 & 1,links  & 7 &  \\ \hline
        7 &   &          &   & Endzustand \\ \hline
    \end{tabular}
\end{table}

Erläuterung: 

Zunächst befindet sich der Lesekopf auf der ersten 1 und da $n \ge 1$ ist
hier keine 0 möglich. Dann läuft der Kopf die ganze Einserkette ab, bis er
eine 0 erreicht (Zustand 2),
diese wird durch eine 1 überschrieben und dann läuft er
weiter bis zur nächsten 0 (Zustand 3), welche beibehalten wird und die
1 davor, wird durch eine 0 ersetzt (Zustand 4).
Danach muss zurück zum Anfang gefunden werden (Zustand 5). Deshalb
wurde das erste Feld im ersten Schritt mit einer 0 markiert, diese wird als
letztes noch durch eine 1 überschrieben (Zustand 6) und dann geht die Maschine in den
Endzustand (Zustand 7).

\end{document}