<aside> ❗ This summary contains all relevant material for the mid- and endterm exam 2021. The content for the session exam or future endterms might be different. E.g. include 10.4.
</aside>
<aside> ❗ This and many more summaries can be found on https://dcamenisch.github.io/ethz-summaries/notes/. Feel free to leave a comment in the document if you spot any mistakes!
</aside>
Definition: Ein Wort über ein Alphabet $\Sigma$ ist eine endliche Folge von Buchstaben aus $\Sigma$. Das leere Wort $\lambda$ ist die leere Buchstabenfolge. $\Sigma^$ ist die Menge aller Wörter über $\Sigma, \Sigma^+$ ist die Menge aller Wörter über $\Sigma^$ ohne das leere Wort.
Definition: $a^R$ bezeichnet die Umkehrung des Wortes $a$.
Definition: $v$ ist genau dann ein echtes Teilwort on $w$, wenn $v \neq \lambda \; \wedge \; v \neq w$.
Definition: Das Entscheidungsproblem für ein gegebenes Alphabet und eine gegebene Sprache, ist zu entscheiden, ob $x \in L, \forall x \in \Sigma^*$. Wenn ein Algorithmus $A$ das Entscheidungsproblem löst, sagen wir $A$ erkennt $L$ und $L$ ist rekursiv.
Definition: Ein Aufzählungsalgorithmus für eine Sprache $L$, gibt für eine Eingabe $n \in \N - \{0\}$ die Wortfolge $x_1, x_2, ... , x_n$ aus. Für eine rekursive Sprache $L$ existiert immer ein Aufzählungsalgorithmus.
<aside> ❗ Die Kolmogorov-Komplexität $K(x)$ eines Wortes $x$ ist das Minimum der binären Länge der Pascal-Porgramme, welche das Wort generieren.
</aside>
Lemma 2.4: Es existiert eine Konstante $d$, so dass für jedes $x \in \Sigma_{bool}^*: K(x) \leq |x| + d$
Lemma 2.5: Für jede Zahl $n \in \N - \{0\}$ existiert ein Wort $x \in \Sigma_{bool}^n$, so dass $K(x) \geq |x| = n$, d.h es existiert ein Wort der Länge $n$, welches nicht komprimierbar ist.
Definition: Ein Wort $x \in \Sigma_{bool}^*$ heisst zufällig, falls $K(x) \geq |x|$. Eine Zahl $n$ heisst zufällig, falls $K(n) \geq K(Bin(n)) \geq \lceil\log_2(n+1)\rceil - 1$.