Entscheidbarkeit < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Zeigen Sie: Sind [mm] M_{1};M_{2}\subseteq X^{\*} [/mm] entscheidbare Mengen, so auch [mm] M_{1}\backslash M_{2};
[/mm]
Meine Frage
Was versteht man unter Entscheidbarkeit.
Ich hatte in der Vorlesung Entscheidbarkeit so versanden:
Gibt es ein Algorithmus der das überprüfen kann, dann ist es entscheidbar.
Der Lehrer hatte mir gesagtr das ist es falsch verstanden habe.
Mein Problem, wenn der Begriff richtig geklärt ist. Wie kann mann die gegebene Aussage richtig beweisen.
Kann mir das jemand an mein Beispiel erklären, wie dieser Begriff richtig zu verstehen ist und wie man das beweist
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:31 Di 04.11.2008 | | Autor: | Christopf |
Kann mir bitte jemand erklären wie ich das Problem lösen muss
Danke im Vorraus
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:58 Do 06.11.2008 | | Autor: | bazzzty |
> Zeigen Sie: Sind [mm]M_{1};M_{2}\subseteq X^{\*}[/mm] entscheidbare
> Mengen, so auch [mm]M_{1}\backslash M_{2};[/mm]
>
> Meine Frage
> Was versteht man unter Entscheidbarkeit.
> Ich hatte in der Vorlesung Entscheidbarkeit so versanden:
>
> Gibt es ein Algorithmus der das überprüfen kann, dann ist
> es entscheidbar.
Das stimmt schon so. Wer es etwas formaler mag: Eine Menge [mm]M[/mm] ist eintscheidbar, wenn die charakteristische Funktion [mm]\chi_M[/mm], die für jedes Element 0 (nicht enthalten) oder 1 (enthalten) zurückliefert, berechenbar ist. Aber wie gesagt: Das ist eine formalere Definition. Dein Verständnis stimmt schon: gibt es einen Algorithmus, der das Enthaltensein entscheiden kann, ist die Menge entscheidbar. WICHTIG: Dieser Algorithmus muß immer terminieren, sowohl bei Elementen aus [mm]M[/mm] als auch bei anderen! Man muß also den Algorithmus anschmeißen können und nach endlicher Zeit eine Antwort JA/NEIN erhalten.
> Der Lehrer hatte mir gesagtr das ist es falsch verstanden
> habe.
Dem kann ich nicht folgen. Du warst höchstens etwas ungenau.
> Mein Problem, wenn der Begriff richtig geklärt ist. Wie
> kann mann die gegebene Aussage richtig beweisen.
> Kann mir das jemand an mein Beispiel erklären, wie dieser
> Begriff richtig zu verstehen ist und wie man das beweist
In Deiner Erklärung: Wenn [mm]M_1[/mm] und [mm]M_2[/mm] entscheidbar sind, dann gibt es Algorithmen [mm]A_{M_1}[/mm] und [mm]A_{M_2}[/mm], die die beiden Mengen entscheiden. Folgender Algorithmus entscheidet dann [mm]M_1\setminus M_2[/mm]:
Wenn [mm]A_{M_1}(x)=\textrm{NEIN}[/mm] oder [mm]A_{M_2}(x)=\textrm{JA}[/mm] gib NEIN zurück
Sonst gib JA zurück.
Das geht natürlich auch mit charakteristischen Funktionen:
Wenn [mm]\chi_{M_1}[/mm] und [mm]\chi_{M_2}[/mm] berechenbar sind,
dann auch [mm]\chi_{M_1\setminus M_2}:= \chi_{M_1}\cdot(1-\chi_{M_2})[/mm]
|
|
|
|
