Entscheidbarkeit < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Zeigen oder widerlegen Sie folgende Aussage: $L [mm] \text{ ist entscheidbar} \Leftrightarrow \overline{L} \text{ ist entscheidbar}$ [/mm] |
Hi Leute!
Ich hab meinen Beweis nun so angefangen:
Beweis:
[mm] "\Rightarrow":
[/mm]
L ist entscheidbar, d.h. L ist rekursiv, d.h. es gibt eine TM M, die L entscheidet, d.h. es gibt eine TM M die für alle $x [mm] \in [/mm] L$ in einem akzeptierenden Zustand hält.
[mm] "\Leftarrow":
[/mm]
[mm] \overline{L} [/mm] ist entscheidbar, d.h. [mm] \overline{L} [/mm] ist rekursiv, d.h. es gibt eine TM M die [mm] \overline{L} [/mm] entscheidet, d.h. es gibt eine TM M die für alle $x [mm] \in \overline{L}$ [/mm] in einem akzeptierenden Zustand hält.
Ich hab nun schon mal beide Richtungen angefangen zu beweisen. Aber irgendwie denke ich, dass das noch nicht so ganz stimmt. Kann mir jemand helfen, zu finden, was hier noch fehlt bzw. was falsch ist?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:48 Fr 07.06.2013 | | Autor: | bandchef |
Ich pushe Einträge von mir ja ungern, aber weiß hier wirklich niemand mehr als ich???
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Sa 08.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
