rekursiv-aufzählbar, Halteprob < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Sei [mm] \Sigma [/mm] ein Alphabet. Zeigen Sie, das jede rekursiv-aufzählbare Sprache [mm] L\subseteq\Sigma\* [/mm] auf das Halteproblem reduzierbar ist. |
Hallo in die Runde 
Ich habe hier noch eine Aufgabe bezüglich des Halteproblems.
Meine Lösung war, dass es für jede rekursiv-aufzählbare Sprache eine Turingmaschine (TM) gibt, die alle Wörter dieser Sprache akzeptiert.
Das Halteproblem besagt, dann dass es keine TM gibt, die überprüfen kann, ob eine andere TM eine bestimmte Sprache akzeptiert.
Da man also zu jeder rekursiv-aufzählbaren Sprache eine TM entwickeln kann und diese TM aber nicht überprüfbar auf ihr Verhalten gegenüber einer Sprache ist, kann man jede rekusrsiv-aufzählbare Sprache auf das Halteproblem reduzieren.
Ist das ausreichend zur Beantwortung dieser Frage? Oder gibt es dafür einen formalen Beweis?
Danke für Eure Antworten.
Grüße
G.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mi 28.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
