Semi-Entscheidbare Sprache < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:46 Fr 13.01.2012 | | Autor: | Dym |
| Aufgabe | | Zeigen Sie, dass jede unendliche semi-entscheidbare Sprache eine unendliche entscheidbare Teilmenge besitzt. (Hinweis: Konstruieren Sie eine Teilmenge, die in lexikographischer Ordnung rekursiv aufzählbar ist). |
Hallo Liebe Community,
ich habe hier eine Übungsaufgabe,die ich beweisen soll.
Ich weiß nicht wie man hier mit dem Beweis anfangen sollte, kann mir jemand eine
Beweisidee geben bitte?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:32 Fr 13.01.2012 | | Autor: | sandp |
> Zeigen Sie, dass jede unendliche semi-entscheidbare Sprache
> eine unendliche entscheidbare Teilmenge besitzt. (Hinweis:
> Konstruieren Sie eine Teilmenge, die in lexikographischer
> Ordnung rekursiv aufzählbar ist).
> Hallo Liebe Community,
>
> ich habe hier eine Übungsaufgabe,die ich beweisen soll.
> Ich weiß nicht wie man hier mit dem Beweis anfangen
> sollte, kann mir jemand eine
> Beweisidee geben bitte?
hey,
am Besten fängst du damit an, dass du zeigst, dass jede unendliche aufzählbare Menge EINDEUTIG aufzählbar ist.
Danach musst du noch zeigen, dass jede unendlich entscheidebare Menge streng monoton aufzählbar ist(und umgekehrt).
Hast du eine Idee wie man zeigt dass jede unendlich aufzählbare Menge EINDEUTIG aufzählbar ist?
den Zusammenhang zwischen semi-entscheidbar und rekursiv aufzählbar kennst du ja?
Gruß sandp
|
|
|
|
