$re = '/(\\\\ (?!item)(?=\w+) ((?!emptyset) (?!dots\s+\\\\\}) (?!in) (?!notin) (?!label) (?!coloneqq) (?!forall) (?!to) (?!exists) (?!subset) (?!Gamma) (?!Sigma) (?!times)(?!geq))\w+[^\S\n]) | (\\\\item\s/mx';
$str = '\\documentclass[Sammlung.tex]{subfiles}
\\part{Einführung}
\\begin{document}
\\begin{comment}
\\begin{defi}
\\end{defi}
\\begin{itemize}
\\end{itemize}
\\end{comment}
Im Rahmen dieser Bachelorarbeit ist $\\mathbb{N} \\coloneqq \\{1, 2, \\dots \\}$.
\\begin{defi}
Sei $\\Omega$ eine nichtleere Menge. Eine \\indiziere{$\\sigma$-Algebra} ist eine Menge $\\mathcal{A} \\subset \\Omega$ mit folgenden Eigenschaften:
\\begin{itemize}
\\item $\\emptyset \\in \\mathcal{A}$.
\\item $\\forall A \\in \\mathcal{A}: A^c \\in \\mathcal{A}$.
\\item $\\forall (A_n)_{n \\in \\mathbb{N}} : (\\forall n \\in \\mathbb{N}: A_n \\in \\mathcal{A}) \\implies \\bigcup_{n = 1}^{\\infty} A_n \\in \\mathcal{A}$.
\\end{itemize}
$(\\Omega, \\mathcal{A})$ heißt \\indiziere{Messbarer Raum}.
\\end{defi}
\\begin{defi}
Sei $\\mathcal{A}$ eine $\\sigma$-Algebra. Ein \\indiziere{Maß} ist eine Funktion $\\mu: \\mathbb{\\mathcal{A}} \\to \\mathbb{R}^+$ mit folgenden Eigenschaften:
\\begin{itemize}
\\item $\\mu(\\emptyset) = 0$.
\\item (\\indiziere{$\\sigma$-Additivität}) Für jede Folge $(A_n)_{n \\in \\mathbb{N}}$ paarweise disjunkter Elemente aus $\\mathcal{A}$ gilt: \\[\\mu(\\bigcup_{n = 1}^{\\infty} A_n) = \\sum_{n = 1}^{\\infty} \\mu(A_n)\\].
\\end{itemize}
$(\\Omega, \\mathcal{A}, \\mu)$ heißt \\indiziere{Maßraum}.
\\end{defi}
\\begin{defi}
Sei zusätzlich $\\Omega \\in \\mathcal{A}$. Dann heißt ein Maß $\\mu$ \\indiziere{Wahrscheinlichkeitsmaß}, falls $\\mu$ ein Maß ist und zusätzlich $\\mu(\\Omega) = 1$ gilt.\\newline
$(\\Omega, \\mathcal{A}, \\mu)$ heißt \\indiziere{Wahrscheinlichkeitsraum}.
\\end{defi}
\\begin{defi}
Sei $U$ eine Grundmenge, genannt \\indiziere{Universum}. Seien $I, J$ Indexmengen, $(n_i)_{i \\in I}$ und $(k_i)_{i \\in I}$ Folgen natürlicher Zahlen, $(f_i)_{i \\in I}$ eine Folge von Funktionen $f_i: U^{n_i} \\to U$ sowie $(R_j)_{j \\in J}$ eine Folge von Relationen $R_j \\subset A^{k_j}$. Dann heißt das Tupel $\\mathcal{A} \\coloneqq \\left(U, (f_i)_{i\\in I}, (R_j)_{j \\in J} \\right)$ eine \\indiziere{Struktur erster Ordnung} auf $U$.
\\emph{Konstanten}\\index{Konstante} sind nullstellige Relationen.
\\end{defi}
Im Folgenden betrachten wir eine Struktur $\\mathcal{A}$ mit endlichem $I$ und nur endlich vielen nicht-nullstelligen Relationen sowie mindestens zwei Konstanten $c_0$ und $c_1$.
\\begin{defi}
Sei $L \\coloneqq \\mathbb{N}$ die Indexmenge und $k_\\mathcal{M}$ eine natürliche Zahl sowie $\\mathcal{A}$ eine Struktur erster Ordnung. Außerdem seien $(Z_l)_{l \\in L}$ eine Folge von \\emph{Registern}\\index{Register}, die je ein Element der Grundmenge $U$ aufnehmen können sowie $I \\coloneqq (I_1, I_2, \\dots, I_{k_{\\mathcal{M}}})$ \\indiziere{Indexregister} für die Adressen einzelner $Z_l$, also natürlicher Zahlen. Dann heißt $\\mathcal{M} \\coloneqq (\\mathcal{M}, (Z_l)_{l \\in L}, I)$ ein \\indiziere{BSS-RAM}, wenn
\\begin{itemize}
\\item sie ein endliches Tupel von Registerbelegungen als Eingabe erhält,
\\item die Eingabelänge über ein Indexregister bei der Eingabe angegeben wird,
\\item die Ausgabelänge nach dem Halt (falls die Maschine hält) in einem Indexregister angegeben ist und
\\item folgende Operationen möglich sind:
\\begin{itemize}
\\item $I_i \\coloneqq 1$
\\item $I_i \\coloneqq I_i + 1$
\\item Verzweigung gemäß Indexregistervergleich
\\item Verzweigung abhängig davon, ob fixe Register in Relation zueinander stehen
\\item \\textbf{STOP}
\\item Kopieren: $Z_{I_1} \\coloneqq Z_{I_2}$
\\item Auswerten: $Z_l \\coloneqq f(Z_{I_1}, Z_{I_2}, \\dots, Z_{I_n})$ für berechenbare Funktionen $f$
\\item $Z_j \\coloneqq c_k$
\\end{itemize}
\\end{itemize}
\\end{defi}
Dabei werden noch vor der eigentlichen Eingabe alle $Z$-Register mit 0 und Indexregister mit 1 initialisiert.
% Wo kommt A überhaupt in der Definition der BSS-RAM vor?
\\begin{defi}
Eine Funktion heißt \\indiziere{$\\mathcal{A}$-berechenbar}, wenn eine BSS-RAM über $\\mathcal{A}$ existiert, die diese Funktion für alle Eingaben in endlicher Zeit berechnet.
\\end{defi}
\\begin{defi}
Sei $U$ ein Universum. Als \\indiziere{Folgenmenge} wird $U^\\infty \\coloneqq \\bigcup_{i = 1}^{\\infty} U^i$ bezeichnet.
\\end{defi}
\\begin{comment}
\\begin{defi}
Sei $U$ ein Universum und $P \\subset P(U)$ eine Menge Teilmengen von $U$. Ein \\indiziere{Operator} im Sinne dieser Bachelorarbeit ist eine Funktion $f: P \\to \\overline{\\mathbb{R}}$.
\\end{defi}
\\end{comment}
Für die Definition eines \\emph{Problems}\\index{Problem} wird auf das Buch \\cite{garey2002computers} verwiesen.
\\begin{defi}
Sei $P$ ein Problem. Dann ist die \\emph{charakteristische Funktion}\\index{Charakteristische Funktion} definiert als $\\chi_P: U^\\infty \\to \\{c_0, c_1\\}$,
\\begin{displaymath}
\\chi_P(\\vec{x}) =
\\begin{cases}
c_0 & \\text{für } \\vec{x} \\in P\\\\
c_1 & \\text{für } \\vec{x} \\notin P
\\end{cases}
\\end{displaymath}
.
\\end{defi}
\\begin{defi}
Eine partielle Funktion $f: X \\rightsquigarrow Y$ heißt \\indiziere{an der Stelle $x$ definiert}, (geschrieben \\indiziere{$f(x) \\downarrow $}), wenn für $x$ ein eindeutig bestimmtes Bild unter $f$ existiert.
\\end{defi}
\\begin{defi}
Sei $\\mathcal{A}$ eine Menge, $U_\\mathcal{A} \\subset \\mathbb{N}$ effektiv aufzählbar über $\\mathcal{A}$ und sei $f: U_{\\mathcal{A}^ \\infty} \\rightsquigarrow {0, 1}$ eine partielle Funktion. $\\kleene{f}{n} \\coloneqq \\min\\limits_{k \\in \\mathbb{N}} \\{ f(x_1, \\dots, x_n k) = 1 \\land (\\forall l < k: f(x_1, \\dots, x_n, l) \\downarrow)\\} $ wird als \\indiziere{Kleene-Operator} bezeichnet.
\\end{defi}
\\begin{defi}
Voraussetzungen wie eben. Dann wird $\\moscho{f}{n} \\coloneqq \\{ y_1 \\in U_\\mathcal{A} \\mid \\exists (y_2, \\dots, y_m): f(x_1, \\dots, x_n, y_1, y_2, \\dots, y_m) = 1 \\} $ als \\indiziere{Moschovakis-Operator} bezeichnet.
\\end{defi}
\\section*{Typen von RAMs}
\\subsection*{Typ-1-BSS-RAMs}
\\subsubsection*{Deterministische BSS-RAMs}
Keine weiteren Fähigkeiten.
\\subsubsection*{Nichtdeterministische BSS-RAMs}
Eine Ratefunktion ermöglicht es, bei Eingabe den Inhalt einer endlichen Anzahl weiterer Register zu raten.
\\subsection*{Typ-2-RAMs}
Zusätzlich ist ein unendlich langes \\emph{read-only}-Eingabeband sowie ein unendlich langes \\emph{write-only}-Eingabeband gegeben.
% Überprüfen!
\\subsection*{Endlichkeit}
\\subsubsection*{Unendliche BSS-RAMs}
können eine Eingabe entweder endlicher oder unendlicher Länge verwenden. Dieser \\textsc{Modus operandi} wird über ein Indexregister festgelegt (mit 0 für endliche oder 1 für unendliche Eingabelänge als Inhalt). Im Falle einer unendlichen Eingabe entfällt die Notwendigkeit für ein Indexregister, das die Länge der Ausgabe angibt.
\\subsubsection*{Endliche BSS-RAMs}
erhalten nur Eingaben endlicher Länge. Sie enden immer nach endlich vielen Schritten, wenn eine Ausgabe erfolgt.
%% RAMs mit endlicher Eingabe, aber unendlich vielen Schritten werden nicht behandelt, oder? Doch. Bei unendlich vielen Schritten erfolgt erst gar keine Ausgabe.
\\subsection*{Endlichdimensionalität}
Eine BSS-RAM heißt \\indiziere{endlich-dimensional}, wenn für alle möglichen Eingaben die Ausgabe stets gleich lang und endlich ist.
\\subsection*{Unendliche Limes-Typ-2-BSS-RAMs}
Fixiere eine Metrik $d$. Dann geben Maschinen dieses Typs den Limes genau dann aus, wenn er in Bezug auf $d$ existiert, insbesondere also endlich ist, nachdem die Folge der Ergebnisse auf das Ausgabeband geschrieben wurde. Über dem geordneten Körper der Reellen Zahlen mit Standardmetrik ist diese Definition äquivalent zu Analytischen Maschinen.
\\subsection*{Starke unendliche (Limes-)Typ-2-BSS-RAMs}
Diese Maschinen sind wie unendliche Limes-Typ-2-BSS-RAMs mit der zusätzlichen Einschränkung, dass der Limes höchstens dann ausgegeben wird, wenn die Folge schneller als $\\frac{1}{2^k}$ bezüglich $d$ konvergiert.
%% Wozu die Kopieroperation von I_1 nach I_0
%% Unendlich als Ausgabe?
%% Indexregister vergessen nichts, weil sie immer wieder auf 1 zurückgesetzt werden können.
%% Z_I_3 := Z_{c(I_3)}
\\section*{Beispiele}
\\subsection*{Endliche Summen}
Eigene Lösung zur Problemstellung in \\cite[11]{skript_berechenbarkeit}.
Das ist eine endlichdimensionale deterministische BSS-RAM.
Eigene Fassung (Annahme: $n \\geq 1$):
\\begin{enumerate}
\\item Eingabe von $x_1, \\dots, x_n$;
\\item if $I_1 == 1$ then GOTO \\ref{itm:AusgabeSumme} /* nur eine Zahl gegeben
\\item \\label{itm:Schleifenbeginn} $I_2 \\coloneqq I_2 + 1$ /* Zählt die aufaddierten Zahlen. (2 = zweite Zahl wird gerade behandelt) und schreitet nach rechts fort
\\item $Z_{1} \\coloneqq Z_{1} + Z_{I_2}$;
\\item if $I_1$ == $I_2$ then GOTO \\ref{itm:AusgabeSumme} else GOTO \\ref{itm:Schleifenbeginn}; /* n == Index der gerade aufaddierten Zahl
\\item \\label{itm:AusgabeSumme} Ausgabe: $Z_{1}$.
\\end{enumerate}
Es folgt eine beispielhafte Durchführung am Beispiel von $x_1 = 1, x_2 = 2, x_3 = 3$ und $x_4 = 4$.\\newline
In der Darstellung steht die erste Reihe Kästchen für die $Z$-Register, gefolgt von den Kästchen für die Indexregister weiter unten. Der besseren Übersicht halber wurde das vom zweiten Indexregister referenzierte Feld eingefärbt.
%% Ausgabeindexregister nicht vergessen!
\\begin{enumerate}
\\item Grundzustand: \\newline
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
\\cellcolor{blue!10} 0 & 0 & 0 & 0 & 0 & 0 & \\dots \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{2}{|c}|}
\\mc{I_1} & \\mc{I_2} \\\\ \\hline
1 & 1 \\\\ \\hline
\\end{tabular}
$Z$-Register werden automatisch mit 0 beziehungsweise Indexregister mit 1 initialisiert.
\\item Initialisierung: \\newline
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
\\cellcolor{blue!10} 1 & 2 & 3 & 4 & 0 & 0 & \\dots \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{2}{|c}|}
\\mc{I_1} & \\mc{I_2} \\\\ \\hline
(n = ) 4 & 1 \\\\ \\hline
\\end{tabular}
Wichtig: Das erste Indexregister enthält die Größe der Eingabe.
\\item Test: $I_1 == 1$? Falsch.
\\item Erster Durchlauf:
\\begin{itemize}
\\item Nächste Zahl: \\newline
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
1 & \\cellcolor{blue!10} 2 & 3 & 4 & 0 & 0 & \\dots \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{2}{|c}|}
\\mc{I_1} & \\mc{I_2} \\\\ \\hline
4 & 2 \\\\ \\hline
\\end{tabular}
\\item Addition: \\newline
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
(1 + 2 = ) 3 & \\cellcolor{blue!10} 2 & 3 & 4 & 0 & 0 & \\dots \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{2}{|c}|}
\\mc{I_1} & \\mc{I_2} \\\\ \\hline
4 & 2 \\\\ \\hline
\\end{tabular}
\\item Test: $I_1 = I_2$? Falsch.
\\end{itemize}
\\item Zweiter Durchlauf: \\newline
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
(1 + 2 + 3 = ) 6 & 2 & \\cellcolor{blue!10} 3 & 4 & 0 & 0 & \\dots \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{2}{|c}|}
\\mc{I_1} & \\mc{I_2} \\\\ \\hline
4 & 3 \\\\ \\hline
\\end{tabular}
\\item Test: $I_1 = I_2$? Falsch.
\\item Dritter Durchlauf: \\newline
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
(1 + 2 + 3 + 4 = ) 10 & 2 & 3 & \\cellcolor{blue!10} 4 & 0 & 0 & \\dots \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{2}{|c}|}
\\mc{I_1} & \\mc{I_2} \\\\ \\hline
4 & 4 \\\\ \\hline
\\end{tabular}
\\item Test: $I_1 = I_2$? Richtig.
\\item Ausgabe: $Z_1 = 10$
\\end{enumerate}
\\subsection*{Reihen}
Es wird eine unendliche deterministische BSS-RAM verwendet.\\newline
Sie entspricht teilweise der oben vorgestellten BSS-RAM zur Addition von $n$ Zahlen. Im unendlichen Fall wird kein Indexregister benötigt, das die Anzahl der Eingabeelemente enthält.
\\begin{enumerate}
\\item Eingabe von $x_1, \\dots, x_n$ (endlicher Fall) oder $x_1, x_2, \\dots$ (unendlicher Fall);
\\item $I_1 \\coloneqq 0$ (endlicher Fall) oder $\\coloneqq 1$ (unendlicher Fall);
\\item if $I_1 == 0$ then GOTO \\ref{itm:endlich} else GOTO \\ref{itm:unendlich} /* endlicher Fall mit um eins nach hinten verschobenen Indexregistern
\\begin{enumerate}
\\item \\label{itm:endlich} $I_3 \\coloneqq I_3 + 1$; /* Zählt die aufaddierten Zahlen. (2 = zweite Zahl wird gerade behandelt) und schreitet nach rechts fort
\\item $Z_{1} \\coloneqq Z_{1} + Z_{I_3}$;
\\item if $I_2$ == $I_3$ then GOTO \\ref{itm:AusgabeReihe} else GOTO \\ref{itm:endlich}; /* $I_2$ == n, $I_3$ == Index der gerade aufaddierten Zahl
\\item \\label{itm:AusgabeReihe} Ausgabe: $Z_{1}$.
\\end{enumerate}
\\item /* unendlicher Fall
\\begin{enumerate}
\\item \\label{itm:unendlich} $I_2 \\coloneqq I_2 + 1$; /* Zählt die aufaddierten Zahlen. (2 = zweite Zahl wird gerade behandelt) und schreitet nach rechts fort
\\item $Z_{1} \\coloneqq Z_{1} + Z_{I_2}$;
\\item GOTO \\ref{itm:unendlich}; /* ewige Schleife
\\item /* Keine Ausgabe, sondern stetiges Weiterlaufen
\\end{enumerate}
\\end{enumerate}
Eine endliche Eingabe
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
\\cellcolor{blue!10} 1 & 2 & 3 & 4 & 0 & 0 & \\dots \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{3}{|c}|}
\\mc{I_1} & \\mc{I_2} & \\mc{I_3} \\\\ \\hline
0 & (n = ) 4 & 1 \\\\ \\hline
\\end{tabular}
liefert
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
(1 + 2 + 3 + 4 = ) 10 & 2 & 3 & \\cellcolor{blue!10} 4 & 0 & 0 & \\dots \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{3}{|c}|}
\\mc{I_1} & \\mc{I_2} & \\mc{I_3} \\\\ \\hline
0 & 4 & 4 \\\\ \\hline
\\end{tabular}
. Eine unendliche Eingabe
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
\\cellcolor{blue!10} 1 & 2 & 3 & 4 & 5 & 6 & \\dots \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{2}{|c}|}
\\mc{I_1} & \\mc{I_2} \\\\ \\hline
1 & 1 \\\\ \\hline
\\end{tabular}
liefert eine nie stoppende Maschine. Zwei Zwischenschritte sind:
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
(1 + 2 + 3 + 4 + 5 = ) 15 & 2 & 3 & 4 & \\cellcolor{blue!10} 5 & 6 & \\dots \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{2}{|c}|}
\\mc{I_1} & \\mc{I_2} \\\\ \\hline
1 & 5 \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{7}{|c}}
\\mc{Z_1} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{3}{L}{\\dots} \\\\ \\hline
(1 + 2 + 3 + 4 + 5 + 6 = ) 21 & 2 & 3 & 4 & 5 & \\cellcolor{blue!10} 6 & \\multicolumn{1}{L}{\\overset{\\rightarrow}{\\dots}} \\\\ \\hline
\\end{tabular}
\\begin{tabular}{*{2}{|c}|}
\\mc{I_1} & \\mc{I_2} \\\\ \\hline
1 & 6 \\\\ \\hline
\\end{tabular}
.
\\subsubsection*{Anmerkungen}
Man kann einfachere Anweisungen als \\enquote{Abkürzungen} nutzen. Sei $c \\in \\mathbb{N}$ konstant (im gesamten Programmbereich). Sei
\\begin{itemize}
\\item $Z_c = ...$. Diese Nutzung einer Konstanten als Index für ein $Z$-Register macht die Maschine nicht mächtiger, denn jede Konstante kann vorher in ein zusätzliches Indexregister geladen werden, das anschließend als Index verwendet wird. Dabei entstehen tatsächlich nur endlich viele neue Indexregister, da das Programm eine endliche Länge hat.
\\item Für ein beliebiges Indexregister $I$ die Anweisung $I \\coloneqq c$. Auch hier kann die Anweisung mit bisherigen Mitteln ausgedrückt werden. Dazu nutzt ersetzt man derartige Anweisungen durch:
\\begin{enumerate}
\\item $I \\coloneqq 1$;
\\item $I \\coloneqq I + 1$;
\\item[3 ... $c-1$.] $I \\coloneqq I + 1$;
\\item[c.] $I \\coloneqq I + 1$;
\\end{enumerate}
\\item Seien $I, J$, analog mit der vorigen Bemerkung ist auch $I$ %% verbessern
\\item \\enquote{i. if not \\textless{} bedingung\\textgreater{} GOTO \\textless{}beginn\\_else\\_zweig\\textgreater{}} wird als Abkürzung festgelegt für \\enquote{i. if \\textless{}bedingung\\textgreater{} then GOTO i + 1 else GOTO \\textless{} beginn\\_else\\_zweig\\textgreater{}}
\\item \\enquote{i. if \\textless{} bedingung1\\textgreater{} or \\textless{} bedingung2\\textgreater{} then GOTO }
\\end{itemize}
%% if verbessern
\\subsection*{Emulierung einer Turing-Maschine}
Eine \\emph{deterministische Turingmaschine}\\index{Deterministische Turingmaschine} ist (nach \\cite{skript_theoinf}) ein Tupel $(Q, \\Sigma, \\Gamma, \\delta, \\square, q_1, Q_E)$ mit den folgenden Bestandteilen:
\\begin{itemize}
\\item $Q$, eine endliche Zustandsmenge
\\item $\\Sigma$, das endliche Eingabealphabet,
\\item $\\Gamma$, das endliche Arbeitsalphabet mit $\\Sigma \\cup \\{\\square\\} \\subset \\Gamma$
\\item $\\delta: Q \\times \\Gamma \\to Q \\times \\Gamma \\times \\{-1, 0, 1\\}$, die Überführungsfunktion
\\item $\\square \\subset \\Gamma \\setminus \\Sigma$, das Leerzeichen (auch \\emph{blank} genannt)
\\item $q_1 \\in Q$, der Startzustand
\\item $Q_E \\subset Q$, die Menge der Endzustände.
\\end{itemize}
Dabei erfolgt eine endliche Eingabe (Markierung kennzeichnet den Startpunkt des Lese-\\,/\\,Schreibkopfes):
\\begin{tabular}{C*{10}{|C}}
\\hline
\\dots & \\square & x_{\\hat{k}} & \\dots & x_{-1} & x_0 & x_1 & \\dots & x_{\\tilde{k}} & \\square & \\dots \\\\ \\hline
\\multicolumn{5}{C}{} & \\multicolumn{1}{C}{\\uparrow} & \\multicolumn{5}{C}{}
\\end{tabular}
Um mit der Materie etwas vertrauter zu werden, soll nun eine Turingmaschine durch eine BSS-RAM emuliert werden. Es genügt, eine \\emph{deterministische} Turingmaschine zu betrachten, denn nichtdeterministische Turingmaschinen können durch deterministische simuliert werden (und natürlich umgekehrt). Der Ansatz besteht darin, die endlich \\enquote{parallelen} Berechnungswege der nichtdeterministischen Turingmaschine hintereinander auszuführen.\\newline
Für eine gegebene Eingabe kann man auch mit dem (konstruktiven) Satz von Cook und Levin die nichtdeterministische Turingmaschine in eine aussagenlogische Formel umwandeln, deren Erfüllbarkeit äquivalent zur polynomiellen Lösbarkeit des gegebenen Probleminstanz ist. Anschließend kann man die Formel mittels einer deterministischen Turingmaschine auf Erfüllbarkeit testen.
Also kennzeichnet der Begriff der Berechenbarkeit bezüglich nichtdeterministischer und deterministischer Turingmaschinen die gleichen Funktionen. Die Komplexität bleibt aber nicht zwingend gleich. Im Rahmen dieser Arbeit zählt aber allein die Frage der Berechenbarkeit. \\newline
Gegeben ist eine deterministische Turingmaschine, die wie oben definiert ist. Zwecks Vereinfachung der Notation setzt man:
\\begin{itemize}
\\item $Q \\eqqcolon \\{q_1, q_2, \\dots, q_p\\}$ mit dem Startzustand $q_1$
\\item $Q_E \\eqqcolon \\{q_{E_1}, q_{E_2}, \\dots, q_{E_{\\hat{p}}} \\}$
\\item $\\Gamma \\eqqcolon \\{b_1, b_2, \\dots, b_i\\}$
\\item $\\Sigma \\eqqcolon \\{\\sigma_1, \\sigma_2, \\dots, \\sigma_{\\hat{i}} \\}$
\\item $k \\coloneqq \\min \\{\\hat{k}, \\tilde{k} \\} $
\\end{itemize}
Die Eingabe wird mittels
\\begin{displaymath}
f(i) = \\begin{cases}
\\{-k, \\dots, k\\} & \\to \\{1, \\dots, 2k + 1 \\} \\\\
i & \\mapsto {\\begin{cases}
2 i + 1& \\text{falls } i \\geq 0 \\\\
- 2 i & \\text{falls } i< 0
\\end{cases}}
\\end{cases}
\\end{displaymath}
(einer Bijektion zwischen $\\mathbb{Z}$ und $\\mathbb{N}$, wenn man die Domänen verändert) in eine besser auf das nur halbseitig unbegrenzte Eingabeband der BSS-RAM passende Form gebracht. Dazu wird $f$ auf die Indizes angewandt.\\newline
Die zu $f$ gehörende Umkehrfunktion ist
\\begin{displaymath}
f^{-1} (j) = \\begin{cases}
\\{0, \\dots, 2k \\} & \\to \\{-k, \\dots, k\\} \\\\
j & \\mapsto {\\begin{cases}
-j / 2 & \\text{falls } j \\text{ gerade} \\\\
(j - 1) / 2 & \\text{falls } j \\text{ ungerade}
\\end{cases}}
\\end{cases}
\\end{displaymath}
Damit sind die $Z$-Register abgedeckt. Nun kümmert man sich um die Indexregister.\\newline
Man benötigt derer vier:
\\begin{itemize}
\\item eines ($I_1$), das die Größe der Eingabe angibt ($2 k + 1$),
\\item eines ($I_2$), das die Ausgabelänge enthalten wird, falls die Maschine stoppt,
\\item eines ($I_3$), dessen Inhalt der Index des aktuellen Zustandes ist und
\\item eines ($I_4$), das die aktuelle Position des Lese-\\,/\\.Schreibkopfes (umgerechnet in BSS-Indizes) angibt.
\\end{itemize}
Das sieht dann so aus:
\\begin{tabular}{*{6}{|C}}
\\mc{Z_{1 ( = f(0))}} & \\mc{Z_2} & \\mc{Z_3} & \\mc{Z_4} & \\multicolumn{2}{L}{\\dots} \\\\ \\hline
x_0 & x_{-1 \\left( = f^{-1}(2)\\right) } & x_{1} & x_{-2} & x_2 & \\dots \\\\ \\hline
\\mc{\\uparrow} & \\multicolumn{5}{C}{}
\\end{tabular}
\\begin{tabular}{*{4}{|c}|}
\\mc{I_1} & \\mc{I_2} & \\mc{I_3} & \\mc{I_4} \\\\ \\hline
\\mc{2 k + 1} & 1 & 1 & 1 \\\\ \\hline
\\end{tabular}
Das Programm ist dann wie folgt:
% f und f^-1 weidlich nutzen!!!
\\begin{enumerate}
\\item \\label{itm:anfang} /* Prüfung, ob ein Endzustand in $I_3$ vorliegt.
\\begin{enumerate}
\\item if $I_3 == E_1$ then GOTO \\ref{itm:ende} else GOTO 2.;
\\item if $I_3 == E_2$ then GOTO \\ref{itm:ende} else GOTO 3.;
\\item[2 - $E_{\\hat{p} - 1}$] \\vdots
\\item[$E_{\\hat{p}}$] if $I_3 == E_{\\hat{p}}$ then GOTO \\ref{itm:ende} else GOTO $E_{\\hat{p} + 1}$;
\\end{enumerate}
\\item /* Die folgenden beiden Zeile steht symbolisch für alle möglichen Stelle-Wert-Kombinationen von $\\delta$.
\\item if $I_3 == i$ und $Z_{I_4} == ...$ then
\\item ...
\\item GOTO \\ref{itm:anfang}
\\item \\label{itm:ende} STOP
\\end{enumerate}
Das Design weist strukturelle Ähnlichkeiten zu modernen GUI-Programmen mit Ereignisschleife auf. Das liegt an ähnlichen Anforderungen. Die Fortschreiten des Lese-\\,/\\,Schreibkopfes auf den veränderten Indizes erfolgt dabei wie folgt:
\\begin{enumerate}
\\item /* $I_4 == 0 \\implies$ Position wird nicht verändert
\\item if $I_4 == 0$ then GOTO \\ref{itm:unterende}
\\item if not $I_4 == 1$ then GOTO \\ref{itm:fall_rueckschritt}
\\begin{enumerate}
\\item /* $I_4$ gleich 1, also soll der Lese-\\,/\\,Schreibkopf auf dem Originalband eins nach rechts rücken.
\\item if
\\end{enumerate}
\\item \\label{itm:unterende} STOP
\\end{enumerate}
\\subsection*{Unterprogramm}
Wenn man
Im Folgenden seien die Mengen $\\{c_0\\}, \\{c_1\\}$ entscheidbar.
\\end{document}';
preg_match_all($re, $str, $matches, PREG_SET_ORDER, 0);
// Print the entire match result
var_dump($matches);
Please keep in mind that these code samples are automatically generated and are not guaranteed to work. If you find any syntax errors, feel free to submit a bug report. For a full regex reference for PHP, please visit: http://php.net/manual/en/ref.pcre.php