www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Komplexität & Berechenbarkeit" - Diagonalbeweis f. rek.Aufzählb
Diagonalbeweis f. rek.Aufzählb < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Diagonalbeweis f. rek.Aufzählb: Antwort ist schon im Posting !
Status: (Frage) reagiert/warte auf Reaktion Status 
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

        
Bezug
Diagonalbeweis f. rek.Aufzählb: Antwort
Status: (Antwort) fertig Status 
Datum: 10:21 Sa 07.01.2006
Autor: mathiash

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

Bezug
                
Bezug
Diagonalbeweis f. rek.Aufzählb: Fortsetzung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Diagonalbeweis f. rek.Aufzählb: Korrektur
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de