%Please use LuaLaTeX or XeLaTeX \documentclass[11pt,aspectratio=169]{beamer} \usepackage[ngerman]{babel} \usepackage{ragged2e} \usepackage[table]{xcolor} \usepackage{array} \definecolor{lightgreen}{RGB}{230,245,232} \definecolor{lightred}{RGB}{255,200,200} \definecolor{lightgrey}{RGB}{240,240,240} \definecolor{ethblue}{RGB}{32, 91, 174} \definecolor{mygrey}{RGB}{175, 175, 175} \hypersetup{ colorlinks=true, urlcolor=ethblue, linkcolor=ethblue, citecolor=ethblue } \title{Theoretische Informatik} % \date[ABC 2021]{24. Sep 2026} \date[]{05. Nov 2026} \author{Olivér Kovács} % \institute{Organizational Unit\\can spread over 2 lines} \usetheme{eth} \colorlet{titlefgcolor}{ETHBlue} \colorlet{accentcolor}{ETHRed} \begin{document} %\def\titlefigure{elements/title-page-image} % Default image %\def\titlefigure{elements/title-page-image-43} % Use this for 4:3 presentations \titleframe % \tocframe % \section{Layout} \begin{frame}{Bemerkungen zur Serie} \textbf{Aufgabe 11} (Hilbert Hotel) \begin{itemize} \item In TI gilt \(0 \in \mathbb N\). \item Es ist egal, wie man nummeriert, aber am Besten erwähnen. \item Konstruktive Lösung wäre schön. (Portier!) \end{itemize} \vspace{1em} \textbf{Aufgabe 12} (Reduktionen) \begin{itemize} \item "Garbage"\ Elemente im Komplement nicht vergessen! \item Korrektheit beweisen. \item Lemma 5.3 zitieren. \end{itemize} \end{frame} \begin{frame}{Quiz} Gibt es Fragen zum Quiz? \end{frame} \begin{frame}{Reduktionen} \justifying \textbf{Lemma (\(*\)).} Für jede Sprache \(L\) gilt \[ L \in \mathcal L_{\text{RE}} \land L^C \in \mathcal L_{\text{RE}} \implies L \in \mathcal L_{\text{R}}. \] \vspace{1em} Beweis? \end{frame} \begin{frame}{Reduktionen} \justifying \textbf{Lemma (\(*\)).} Für jede Sprache \(L\) gilt \[ L \in \mathcal L_{\text{RE}} \land L^C \in \mathcal L_{\text{RE}} \implies L \in \mathcal L_{\text{R}}. \] \vspace{1em} \textbf{Beweis:} Seien \(M_1, M_2\) TMs mit \(L(M_1) = L(M_2)^C = L\). Die TM \(M\) simuliert abwechselnd \(M_1, M_2\) auf gegebenes \(w\), akzeptiert falls \(M_1\) akzeptiert, verwirft falls \(M_2\) akzeptiert. Da \(w \in L\) oder \(w \in L^C\) hält \(M\) immer und \(L(M) = L\). \end{frame} \begin{frame}{Übersicht Beweisideen} \makebox[\textwidth][c]{ \begin{tabular}{|l|l|l|l|} \hline \(L\) & \(L \not\in \mathcal L_{\text{R}}\) & \(L \in \mathcal L_{\text{RE}}\) & \(L \not\in \mathcal L_{\text{RE}}\) \\ \hline \(L_{\text{diag}}\) & \cellcolor{lightgreen}\checkmark & \cellcolor{lightred}- & \cellcolor{lightgreen}Diag.-argument 2 \\ \((L_{\text{diag}})^C\) & \cellcolor{lightgreen}\(^{\mathcal L_{\text{R}} \not\ni} L_{\text{diag}} \le_{\text{R}} (L_{\text{diag}})^C\) & \cellcolor{lightgreen}\((L_{\text{diag}})^C \le_{\text{EE}} L_{\text U} ^{\hspace{0.2em}\in \mathcal L_{\text{RE}}}\) & \cellcolor{lightred}- \\ \(L_{\text{U}}\) & \cellcolor{lightgreen}\(^{\mathcal L_{\text{R}} \not\ni} (L_{\text{diag}})^C \le_{\text{R}} L_{\text U}\) & \cellcolor{lightgreen}TM & \cellcolor{lightred}- \\ \((L_{\text{U}})^C\) & \cellcolor{lightgreen}\checkmark & \cellcolor{lightred}- & \cellcolor{lightgreen}(\(*\)), \(^{{L_{\text U}} \in \mathcal L_{\text{RE}} \setminus \mathcal L_{\text R}\dagger}\) \\ \(L_{\text{H}}\) & \cellcolor{lightgreen}\(^{\mathcal L_{\text{R}} \not\ni} L_{\text U} \le_{\text{R}} L_{\text H}\) & \cellcolor{lightgreen}\(L_{\text{H}} \le_{\text{EE}} {L_{\text U}} ^{\in \mathcal L_{\text{RE}}}\) & \cellcolor{lightred}- \\ \((L_{\text{H}})^C\) & \cellcolor{lightgreen}\checkmark & \cellcolor{lightred}- & \cellcolor{lightgreen}(\(*\)), \(^{{L_{\text H}} \in \mathcal L_{\text{RE}} \setminus \mathcal L_{\text R}\dagger}\) \\ \(L_{\text{empty}}\) & \cellcolor{lightgreen}\checkmark & \cellcolor{lightred}- & \cellcolor{lightgreen}(\(*\)), \(^{(L_{\text{empty}})^C \in \mathcal L_{\text{RE}} \setminus \mathcal L_{\text R}\dagger}\) \\ \((L_{\text{empty}})^C\) & \cellcolor{lightgreen}\(^{\mathcal L_{\text{R}} \not\ni} L_{\text U} \le_{\text{R}} (L_{\text{empty}})^C\) & \cellcolor{lightgreen}(N)TM & \cellcolor{lightred}- \\ \(L_{\text{EQ}}\) & \cellcolor{lightgreen}\checkmark & \cellcolor{lightred}- & \cellcolor{lightgreen}\(^{\mathcal L_{\text{RE}} \not\ni\dagger} L_{\text{empty}} \le_{\text{EE}} L_{\text{EQ}}\) \\ \((L_{\text{EQ}})^{C\dagger}\) & \cellcolor{lightgreen}\checkmark & \cellcolor{lightred}- & \cellcolor{lightgreen}\(^{\mathcal L_{\text{RE}} \not\ni} (L_{\text H})^C \le_{\text{EE}} (L_{\text{EQ}})^{C}\) \\ \(L_{\text{H},\lambda}\) & \cellcolor{lightgreen}\(^{\mathcal L_{\text{R}} \not\ni} L_{\text{H}} \le_{\text{R}} L_{\text{H},\lambda}\) & \cellcolor{lightgreen}\(L_{\text{H},\lambda} \le_{\text{EE}} {L_{\text H}}^{\in \mathcal L_{\text{RE}}\dagger}\) & \cellcolor{lightred}- \\ \hline \end{tabular} } \vspace{0.5em} \tiny{ \textbf{Anm.} \quad -: \textit{falsch} \quad \checkmark: \(L \not\in \mathcal L_{\text{RE}} \implies L \not\in \mathcal L_{\text{R}}\) \quad TM/(N)TM: \textit{direkte Konstruktion} \quad (\(*\)): \textit{\(L, L^C \in \mathcal L_{\text{RE}} \implies L \in \mathcal L_{\text{R}}\)} \quad \(\dagger\): \textit{nicht behandelt} } \end{frame} \begin{frame}{Semantisch nichttrivale Entscheidungsprobleme} \justifying \textbf{Definition 5.7.} Eine Sprache \(L \subseteq \text{KodTM}\) heisst \textit{semantisch nichttriviales Entscheidungsproblem über Turingmaschinen}, falls gilt: \begin{enumerate} \item \(L \neq \varnothing\), \item \(L \neq \text{KodTM}\), und \item für alle TM \(A\) und \(B\) impliziert \(L(A) = L(B)\), dass \[ \text{Kod}(A) \in L \iff \text{Kod}(B) \in L. \] \end{enumerate} \end{frame} \begin{frame}{Spezifisches Halteproblem} \textbf{Definition.} Sei \(L_{\text{H},\lambda}\) die Sprache \[ L_{\text{H},\lambda} = \{\text{Kod}(M) \mid M \text{ hält auf } \lambda\}. \] \vspace{1em} \textbf{Lemma 5.8.} Es gilt \(L_{\text{H},\lambda} \not\in \mathcal L_{\text{R}}\) . \vspace{1em} Beweis? \end{frame} \begin{frame}{Der Satz von Rice} \justifying \textbf{Satz 5.9 (Satz von Rice).} Jedes semantisch nichttriviale Entscheidungsproblem über Turingmaschinen ist unentscheidbar. \end{frame} \begin{frame}{Midterm survival guide} \begin{itemize} \item Schlaft genug \item Stresst euch nicht zu viel \item Nimmt eine dumme Uhr mit \item Liest Angaben genau \item Schaut alle Aufgaben an, löst die einfachen zuerst \end{itemize} \end{frame} \begin{frame}{Midterm survival guide} \justifying Überprüfe \begin{itemize} \item EAs: \begin{itemize} \item Startzustand markiert? \item Akzeptierenden Zustände markiert? (insbesondere Startzustand!) \end{itemize} \item DEAs: \begin{itemize} \item Jeder Zustand hat genau eine ausgehende Kante pro Buchstabe. \item Insbesondere hat jeder Zustand \(|\Sigma|\) ausgehende Kanten. \end{itemize} \item PL: \(|w| \ge n_0\) erwähnt? \item Reduktion: \begin{itemize} \item Wörter mit falschem Format behandelt? \end{itemize} \end{itemize} \end{frame} \begin{frame}{Midterm survival guide} \justifying Ansätze \begin{itemize} \item Grenzfälle betrachten \begin{itemize} \item Insbesondere bei Aussagen über \(L_1 \cap L_2, L_1 \cup L_2, L_1 \setminus L_2, L_1 L_2, \ldots\): Falls möglich setze \(L_1 = L_2\), \(L_1 = L_2^C\), \(L_2 = \varnothing\), usw. \\ Wohlbekannte Beispiele einsetzen. \end{itemize} \item Bei Minimalitätsbeweis: Falls man keine Wörter für Beweis finden kann Automat skizzieren, für jeden Zustand ein Wort suchen, der darin landet. \item Bei PL: Man darf Wörter rein- und rauspumpen. \item Denkt an \(\lambda\). \end{itemize} \end{frame} \begin{frame}{Midterm survival guide} \justifying Beispiele \vspace{1em} Sei \(\Sigma\) ein Alphabet (endlich, nichtleer). \begin{itemize} \item Abzählbar: \(\mathbb N\), \(\mathbb Z\), \(\mathbb Q\), \(\Sigma\), \(\Sigma^*\), \(\text{KodTM}\), Menge aller endlichen Sprachen ü. \(\Sigma\) \item Überabzählbar: \([0, 1]\), \(\mathbb R\), Menge aller Funktionen \(f : \mathbb N \to M\), Menge aller unendlichen Wörter über \(\Sigma\), Menge aller Sprachen über \(\Sigma\). \end{itemize} \vspace{1em} Seien \(L_1, L_2\) regulär, \(L_3\) nicht regulär, \(L_4\) endlich. \begin{itemize} \item Regulär: \(L_1^C\), \(L_1 \cap L_2\), \(L_1 \cup L_2\), \(L_1 \setminus L_2\), \(L_4\), \(\{w \mid |w|_a \equiv_m n\}\), \(\{w \mid u \text{ ist Präfix/Infix/Suffix von } w\}\) \item Nicht regulär: \(L_3^C\), \(\{a^{n^2}\}\), \(\{a^{2^n}\}\), \(\{a^p \mid p \in \mathbb P\}\), \(\{w \mid |w|_a \ge |w|_b\}\), verschachtelte Klammern \end{itemize} \end{frame} % \setbeamertemplate{footline}{} \begin{frame}{Aufgaben} \justifying \begin{enumerate} \item \textbf{Aufgabe 1.} Verwende den Satz von Rice, um \(L_{\lambda + 1} \not\in \mathcal L_{\text{R}}\) zu beweisen. \[ L_{\lambda + 1} = \{\text{Kod}(M) \mid \text{TM } M \text{ akzeptiert } \lambda \text{ und mindestens ein anderes Wort}\} \] \item \textbf{Aufgabe 2.} Beweise \((L_{\text{EQ}})^C \not\in \mathcal L_{\text{RE}}\). \\ \textit{Hint: Beweise \((L_{\text{H}})^C \not\in \mathcal L_{\text{RE}}\) und \((L_{\text{H}})^C \le_{\text{EE}} (L_{\text{EQ}})^C\).} \item \textbf{Aufgabe 3.} Eine TM \(M\) heisst \textit{hastig}, falls ein Wort \(w\) existiert, so dass \(M\) auf \(w\) nach höchstens \(|w|/2\) Schritten hält. Sei \(L_{\text{hasty}}\) die Sprache \[ L_{\text{hasty}} = \{\text{Kod}(M) \mid M \text{ ist eine hastige TM}\}. \] Beweise, dass \((L_{\text{hasty}})^C \not\in \mathcal L_{\text{RE}}\). \item Oder was auch immer ihr noch besprechen möchtet! \end{enumerate} \end{frame} \end{document}