Berechenbarkeit/Aufzählbarkeit < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen Sie:
Eine nichtleere, aufzählbare Sprache L [mm] \subseteq \Sigma^\* [/mm] ist das Bild einer totalen berechenbaren Funktion f: [mm] \Sigma^\* \rightarrow \Sigma^\*. [/mm] |
Hallo liebes Forum,
für den o.g. Satz gilt sogar die Äquivalenz, ich komme aber bei der angegebenen Richtung nicht weiter.
- Erst einmal zum Verständnis:
Ich betrachte also eine nichtleere Sprache L [mm] \subseteq \Sigma^\*, [/mm] die aufzählbar ist; d.h. es existiert ein Algorithmus A, der (mit leerer Eingabe gestartet) alle Wörter aus L "ausspuckt" und i.a. nicht stoppt.
Nun soll es also eine Funktion f geben mit L = Bild(f), und zwar so, daß f total auf [mm] \Sigma^\* [/mm] ist, also für jedes Eingabewort w eine Ausgabe liefert.
- Meine Idee:
Es sei [mm] v\in [/mm] L beliebig (L ist lt. Vor. nicht leer). Betrachte die Funktion f:
f: [mm] \Sigma^\* \rightarrow \Sigma^\* [/mm] , [mm] w\mapsto\begin{cases} w & {\rm falls}\,\, w\in L \\ v & {\rm falls}\,\, w\not\in L. \end{cases}
[/mm]
Offenbar gilt L = Bild(f).
- Problem: Ich kann nicht zeigen, daß diese Funktion f berechenbar ist ;-(
Angenommen, ich starte für jedes [mm] w\in\Sigma^\* [/mm] den Aufzählungsalgorithmus A (mit leerer Eingabe). Ich vergleiche dann jede Ausgabe von A mit dem jeweiligen w. Falls [mm] w\in [/mm] L, gibt A irgendwann w aus, und ich weiß dann, daß [mm] w\in [/mm] L gilt. Falls aber [mm] w\not\in [/mm] L, gibt A nicht w aus und terminiert evtl. nicht. Dann terminiert auch mein Algorithmus nicht bzw. "hängt fest".
- Hat jemand eine Idee, wie es funktioniert?!
Danke!!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:21 Do 18.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
