Formale Sprachen: Beweis von entscheidbarkeit

07.06.2013, 10:50	bandchef	Auf diesen Beitrag antworten »
Formale Sprachen: Beweis von entscheidbarkeit Hi Leute! Ich hab folgende Aufgabe: Beweisen Sie dass gilt: $\begin{eqnarray} L \text{ ist entscheidbar } \Leftrightarrow \overline{L} \text{ ist entscheidbar} \end{eqnarray}$ Beweis: $\begin{eqnarray} " \Rightarrow " \end{eqnarray}$ L ist entscheidbar, d.h. L ist rekursiv, d.h. es gibt eine TM M, die L entscheidet. $\begin{eqnarray} " \Leftarrow " \end{eqnarray}$ $\begin{eqnarray} \overline{L} \end{eqnarray}$ ist entscheidbar, d.h. L ist rekursiv, d.h. es gibt eine TM $\begin{eqnarray} \overline{M} \end{eqnarray}$ die $\begin{eqnarray} \overline{L} \end{eqnarray}$ entscheidet. Kann mir jemand helfen den Beweis fertig zu machen bzw. überhaut zu sagen, ob das bisher so passt...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »