Seite 10/11

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

Seite 32

Seite 33