Vorlesung 4 Grüning
Inhaltsverzeichnis |
Seite 10/11
\frac{\sqrt{8 \cdot \frac{(w+1)^2 + w + 1}{2} + 1} - 1}{2}
Seite 26
entscheidbar: \chi liefert für alle Wörter ob sie in der Menge M sind oder nicht und ist berechenbar
aufzählbar: total surjektive berechenbare Funktion welche \mathbf{N} \rightarrow M
Wenn M entscheidbar dann M aufzählbar
Wir iterrieren durch A^* g: \mathbf{N} \rightarrow A^*. Wir bekommen somit alle Wörter von A^* und fragen die charakteristische Funktion \chi, ob das Wort w in M ist oder nicht. Falls nicht dann bildet man n auf ein Element aus M (a) ab. Falls es enthalten ist, dann n \rightarrow w
Falsch: Wenn M aufzählbar dann M entscheidbar
Notbremse nicht immer vorhanden
Seite 28
entscheidbar: \chi liefert für alle Wörter ob sie in der Menge M sind oder nicht und ist berechenbar
aufzählbar: total surjektive berechenbare Funktion welche \mathbf{N} \rightarrow M
Wenn M entscheidbar, dann M und A^* \setminus M aufzählbar
Wir iterrieren durch A^* g: \mathbf{N} \rightarrow A^*. Wir bekommen somit alle Wörter von A^* und fragen die charakteristische Funktion \chi, ob das Wort w in M ist oder nicht. M: Falls nicht dann bildet man n auf ein Element aus M (a) ab. Falls es enthalten ist, dann n \rightarrow w A^* \setminus M: Falls nicht dann n \rightarrow w. Falls es enthalten ist, dann n \rightarrow a aus A^* \setminus M