Diagonalbeweis f. rek.Aufzählb < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 15:32 Fr 06.01.2006 | | Autor: | Flugzwerg |
| Aufgabe | Definieren Sie durch Diagonalisierung eine Menge A [mm] \subseteq \IN,
[/mm]
die nicht rekursiv aufzählbar ist. |
Hallo!
Mathiash hat mir diese Frage schon beantwortet, da sie aber vielleicht von allgemeinem Interesse ist habe ich sie hier incl. Antwort noch mal online gestellt.
Bei der oben gestellten Aufgabe habe ich Schwierigkeiten!
Ich soll durch Diagonalisierung eine Menge A Teilmenge von [mm] \IN [/mm] zeigen die nicht rekursiv aufzählbar ist.
Das heisst meines Erachtens ich brauche eine Menge die nicht Entscheidbar ist.
Wenn ich das mit Cantors Diagonale zeigen soll, dann brauche ich eine Menge die überabzählbar ist!
( Korrigiert mich bitte wenns Unsinn ist!)
Der Diagonal Beweis wurde in meinem tollen Skript auf einer halben Seite abgehandelt.
Ich bin nun zu der Ansicht gekommen wenn ich eine überabzählbare Menge finde, und eine Funktion dazu die nicht berechenbar ist, dann ist das der Diagonal Beweis nach Cantor! ? !
Desweiteren irritiert mich das meine Menge aus $ [mm] \IN [/mm] $ sein soll.
Die Menge der natürlichen Zahlen
doch abzählbar.
Und hier ist auch mein Problem.
Wie komme ich jetzt von N nach R ????
Liebe Grüße,
Nicole
Antwort von Mathiash:
Hallo Nicole,
es ist zwar $ [mm] \IN [/mm] $ abzaehlbar, aber die Potenzmenge von $ [mm] \IN [/mm] $ hat die gleiche Kardinalitaet
wie $ [mm] \IR, [/mm] $ und es gibt aber nur abzaehlbar viele rek. aufz. Mengen.
ZB nimm eine partiell rek. Funktion $ [mm] U\colon \IN^2\to \IN, [/mm] $ so dass
mit der Definition $ [mm] u_i(n) [/mm] $ := U(i,n)
$ [mm] \{u_i|i\in\IN\} [/mm] $ = die Menge der einstelligen partiell rek Funktionen ist.
Solch eine Funktion U - man nennt sie universelle Fkt. fuer $ [mm] F_{\mu}^{(1)} [/mm] $
gibt es, es ist zwar etwas technisch, sie zu konstruieren, aber nicht essentiell tiefliegend.
Jedenfalls hast Du dann $ [mm] F_{\mu}^{(1)} [/mm] $ = $ [mm] \{u_i|i\in\IN\}. [/mm] $
Nun nimm einfach die Menge
M = $ [mm] \{i\in\IN | i\not\in dom ( u_i)\} [/mm] $
wobei $ [mm] dom(u_i) [/mm] $ der Domain , also der definitionsbereich von $ [mm] u_i [/mm] $ ist.
Dann kann keine der $ [mm] u_i's [/mm] $ die Eigenschaft dom $ [mm] (u_i)=M [/mm] $ haben, also ist M nicht
$ [mm] \mu-rekursiv. [/mm] $
Uebrigens: das waere doch eine interessante Frage fuers Forum, koennt man das da
nicht noch - inklusive der Antwort irgendwie reinschreiben ?
Viele Gruesse,
Mathias
|
|
| |
|
Hallo zusammen,
ich schreib folgende Anmerkung mal als ''Antwort'', um auf gruen zu schalten.
Beim Halteproblem geht man ja beweistechnisch analog vor, um zu zeigen, dass es nicht
rekursiv ist. (Was ist denn das Halteproblem im Vergleich zu der Menge M in der Loesung ?  )
Zeigt man also mit dem Diagonalisierungsbeweis fuers Halteproblem K lediglich, dass dieses nicht rekursiv ist ? Existenz nicht-rekursiver Mengen haette man ja einfacher ueber
ein Abzaehlargument bekommen koennen.
Nein, man zeigt mehr: K ist eine Menge, die rekursiv aufzaehlbar, aber nicht rekursiv ist, und DIES haette man mit einem Kardinalitaetsargument NICHT erhalten koennen, denn beide, die Menge der rek. mengen und die Menge der rek. aufz. Mengen sind
ABZAEHLBAR.
Es gilt mehr: K ist vollstaendig fuer die Menge der rek. aufz. Mengen unter [mm] \leq_m.
[/mm]
Warum folgt jetzt uebrigens aus der Nicht-Rekursivitaet von K schon die
Nicht-Rekursiv-Aufzaehlbarkeit der Menge M aus dem Beweis ?
Koennt ja sein, dass ausser Nicole noch andere diese Dinge demnaechst mal
brauchen koennen - liebe Gruesse an all diejenigen !!!
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:12 Mo 09.01.2006 | | Autor: | mathiash |
Hallo Freunde der Rekursionstheorie,
also es ist wie folgt:
K ist genau das Komplement der Menge M aus der Konstruktion in dem posting von Nicole.
Also allgemein: Sei A eine rekursiv aufzaehlbare Menge, die nicht rekursiv ist. Kann dann
das Komplement [mm] \overline{A} [/mm] rek. aufz. sein ?
Nein.
Denn allgemein gilt ja, dass A rekursiv gdw A und [mm] \overline{A} [/mm] rekursiv aufzaehlbar sind.
Dabei ist [mm] (\Rightarrow [/mm] ) klar, und zu [mm] (\Leftarrow [/mm] ) laesst man bei Eingabe x einfach die
beiden Algorithmen zu A und [mm] \overline{A} [/mm] simultan laufen - genau einer wird halten und
damit die Information geben, ob [mm] x\in [/mm] A oder [mm] x\in \overline{A} [/mm] ist.
Uebrigens ist auch folgende Charakterisierung manchmal hilfreich:
[mm] A\subseteq\IN^k [/mm] ist rekursiv gdw A ''geordnet rek. aufz. ist, d.h. es gibt eine monoton steigende Funktion [mm] f\colon \IN\to\IN^k [/mm] mit [mm] f(\IN) [/mm] =A (A = Bild von f).
(Um die Korrektheit nachzuvollziehen, ueberlege man sich die Faelle
|A| [mm] <\infty [/mm] und |A| [mm] =\infty [/mm] getrennt.)
Noch eine Anmerkung:
Es ist ja das Halteproblem K vollstaendig fuer RE (Menge der rek. aufz. Mengen)
unter [mm] \leq_m, [/mm] der sog. many-one-Reduktion (ein Problem [mm] A\subseteq\IN^k [/mm] ist auf
ein problem [mm] B\subseteq\IN^n [/mm] many-one-reduzierbar (m-reduzierbar) gdw es eine
rekursive Funktion [mm] f\colon\IN^k\to\IN^n [/mm] gibt mit [mm] f^{-1}(B)=A).
[/mm]
Es gibt auch Probleme in RE - der Menge der rek. aufz. Probleme - , die weder rekursiv
noch vollstaendig sind - sogenannte ''intermediate'' Probleme.
Dazu spaeter vielleicht mehr....
Liebe Gruesse,
Mathias
rekursive Funktion f
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:34 Mo 01.02.2010 | | Autor: | info-man |
Hi,
ich bin selber noch schwer am kämpfen mit dem Diagonalbeweis. Allerdings ist die zweistellige N Menge, also zweier Tupel aus den Natürlichen Zahlen nicht anderes als Rationale Zahlen.
Dementsprechend könnte man mit der Canrorischen Paarungsfunktion diese wieder auf die Menge der Natürlichen Zahlen abbilden. Sind also gleichmächtig.
Die Lösung muss woanders liegen.
Grüße
|
|
|
|
