Halteproblem < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:22 Sa 02.06.2012 | | Autor: | Blubie |
| Aufgabe | H ist das Halteproblem und A eine Sprache.
Wenn A [mm] \le [/mm] H und A [mm] \le \overline{H}, [/mm] dann ist A entscheidbar. Zeigen sie oder widerlegen sie. |
Hallo, ich habe eine Reihe von Aufgaben die alle nach demselben Schema aufgebaut sind (die erste ist die obere). Allerdings weiß ich nicht richtig wie ich da ran gehen soll.
Also was ich weiß ist folgendes:
es existiert f (berechenbar), so dass x [mm] \in [/mm] A [mm] \gdw [/mm] f(x) [mm] \in [/mm] H
es existiert g (berechenbar), so dass x [mm] \in [/mm] A [mm] \gdw [/mm] g(x) [mm] \not\in [/mm] H
Weiterhin habe ich folgenden Satz:
C [mm] \le [/mm] D, D entscheidbar [mm] \Rightarrow [/mm] C entscheidbar
Ich vermute mal, dass ich mir mit f und g eine neue, berechenbare Funktion konstruieren kann, die gerade A berechnet aber ich weiß einfach nicht wie. Oder ist A gar nicht berechenbar?
Ich bin für jeden Hinweis dankbar :)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Mo 04.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
