Many-One-Reduzierbarkeit < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweisen Sie die Folgenden Eigenschaften der Many-One-Reduzierbarkeit:
(i) Je zwei rekursive Mengen [mm]A,B \subseteq \IN[/mm] mit [mm]A,B \not\in \{\emptyset,\IN\}[/mm] sind Many-One-äquivalent.
... |
Hallo,
diese Frage gilt es zu lösen. Leider komme ich nicht weiter, ich möchte mein Vorgehen bisher aber mal schildern.
Zuallererst habe ich mir raus gesucht, wie denn Many-One-Reduzierbarkeit definiert ist:
Mengen: [mm]A,B \subseteq \IN[/mm]
A ist Many-One-reduzierbar, wenn ein f existiert, sodass gilt: [mm]\forall n \in \IN: n \in A \gdw f(n)\in B[/mm]
Man schreibt dann [mm]A \le_{m} B via f[/mm]
Als nächstes habe ich mir raus gesucht, was Many-One-Äquivalenz ist:
Die Mengen [mm]A,B \subseteq \IN[/mm] heißen Many-One-äquivalent ([mm]A =_{m} B[/mm]), falls [mm]A \le_{m} B[/mm] und [mm]B \le_{m} A[/mm] gilt.
Ich muss also zeigen, dass f und g existieren, für die gilt:
[mm]\forall n \in \IN: n \in A \gdw f(n)\in B[/mm]
und
[mm]\forall n \in \IN: n \in B \gdw g(n)\in A[/mm]
Nun habe ich mir angesehen, was für rekursive Mengen gilt. Rekursive Mengen sind entscheidbare Mengen, d.h. deren charakteristische Funktion c ist berechenbar.
Also gilt zusätzlich noch:
[mm]c_{A}(x) = c_{B}(f(x))[/mm]
und
[mm]c_{B}(x) = c_{A}(g(x))[/mm]
Soweit so gut. Jetzt komme ich leider nicht mehr weiter. Reichen die Annahmen die ich habe aus oder brauche ich noch etwas? Wie gehe ich hier weiter vor?
Für Hilfe wäre ich sehr dankbar,
Gruß Tim
|
|
| |
|
> Rekursive Mengen sind entscheidbare Mengen, d.h. deren
> charakteristische Funktion c ist berechenbar.
>
> Also gilt zusätzlich noch:
> [mm]c_{A}(x) = c_{B}(f(x))[/mm]
> und
> [mm]c_{B}(x) = c_{A}(g(x))[/mm]
Kann ich das nutzen um folgende Gleichung aufzustellen?
[mm]x \in A[/mm] und [mm]y \in B[/mm]: [mm]c_{A}(x)=c_{B}(f(x))=c_{B}(y)=c_{A}(g(y))[/mm] [mm] \gdw [/mm] f(x)=y und g(y)=x
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Di 26.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Mo 25.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
