Hannes Straß

In VL 20 wird eine zuvor betrachtete TM als LBA interpretiert (lecture-20.tex, ab Zeile 376). Insbesondere gibt es einen Schritt „Akzeptiere, falls der Inhalt des Bandes die Form `\hat{a}^*\hat{b}^*\hat{c}^*` hat“....

Das Lemma fällt quasi „vom Himmel“ – ich schlage folgende Herleitung bzw. Illustration einer möglichen gedanklichen Herkunft vor: `\begin{frame}\frametitle{Gleichungssysteme Lösen (2)} \emph{Problem:} Rekursive Gleichungen lassen sich durch Einsetzen nicht vereinfachen...

lecture-01.tex, Zeile 200: Folgender [Link](https://www.researchgate.net/profile/Christel-Baier/publication/267409804_Formale_Systeme_WS_20112012_Skript_zur_Vorlesung/links/54e24b020cf2966637965e77/Formale-Systeme-WS-2011-2012-Skript-zur-Vorlesung.pdf) kann verwendet werden: `{\tiny Siehe \url{https://www.researchgate.net/profile/Christel-Baier/publication/267409804_Formale_Systeme_WS_20112012_Skript_zur_Vorlesung/links/54e24b020cf2966637965e77/Formale-Systeme-WS-2011-2012-Skript-zur-Vorlesung.pdf}}`

### Problem Im vereinfachten Beweis des 1. Unvollständigkeitssatzes wird die Gödel-Formel F mit dem Inhalt „F ist wahr genau dann wenn F nicht beweisbar ist“ eingeführt. In Zeile 216 wird...

Bei den Konventionen zur Vereinfachung der Syntax könnte auch die Konvention „unäre Junktoren (Negation und Quantoren) binden stärker als binäre Junktoren“ mit aufgeführt werden. Diese scheint später implizit verwendet zu...

In VL17 Zeile 460 steht ein Äquivalenzsymbol `\equiv` zwischen einer Formel und ihrer Skolemisierung. Aus dem Rest der Vorlesung geht zwar eindeutig hervor, dass Skolemisierung nicht äquivalenzerhaltend ist, dies kann...

Um NP-Vollständigkeit von „Unabhängige Menge“ zu zeigen, muss Enthaltensein in NP und NP-Schwere gezeigt werden. Die Reduktion auf Clique zeigt nur Enthaltensein. Dieselbe Funktion (Graphen auf Komplementgraphen abbilden) funktioniert natürlich...