Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Beweis (semi-entscheidbar <=> rekursiv aufzählbar)
Gehe zu Seite 1, 2  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Beweis (semi-entscheidbar <=> rekursiv aufzählbar)
 
Autor Nachricht
Knusperkekse
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 25.09.2007
Beiträge: 57

BeitragVerfasst am: 23 Jan 2008 - 14:59:04    Titel: Beweis (semi-entscheidbar <=> rekursiv aufzählbar)

Hallo,

ich muss folgenden Satz beweisen:

Es gibt eine Turingmaschine M mit L(M) = L genau dann, wenn es eine berechenbare Funktion f mit dom(f) = L gibt.

Leider fallen mir Beweise immer sehr schwer.
Verkürzt bedeutet ja der Satz, wenn ich das richtig sehe, soviel wie semi-entscheidbar <=> rekursiv aufzählbar.
Nur wie zeigt man das denn? Ich will gar keine Lösung hören, nur ich hab keine Ahnung wie ich da jetzt vorgehe.

Ich hoffe auf Hilfe.
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 23 Jan 2008 - 15:26:10    Titel:

Wie genau habt ihr L(M) definiert? Als die Menge aller Wörter, auf der M hält?

Und wie habt ihr dom(f) für eine berechenbare Funktion f definiert? Als die Menge aller Eingaben, auf der eine TM, die f berechnet, hält?


Cyrix
Knusperkekse
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 25.09.2007
Beiträge: 57

BeitragVerfasst am: 23 Jan 2008 - 15:33:16    Titel:

Hi,

L(M) ist die von M erkannte Sprache, also die Wörter für die M stoppt.
L(M) = {w | M akzeptiert w}

Das mit dem dom(f) kam so nicht explizit vor aber ich denke es sind alle Eingaben für die die Turingmaschine stoppt, also alle w aus L.
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 23 Jan 2008 - 15:37:18    Titel:

Naja, dann hast du es doch. Smile

==>
Nimm einfach die Funktion, welche jedes Wort x auf den Bandinhalt von M, gestartet auf x, wenn die Maschiene dann stoppt, abbildet.

und umgekehrt geht es ähnlich schnell... Wink


Cyrix
Masor
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 16.07.2006
Beiträge: 256

BeitragVerfasst am: 23 Jan 2008 - 15:39:29    Titel:

Der allgemeine Beweis semi-entscheidbar <=> rekursiv aufzählbar ist aber nur in die eine Richtung trivial, für die andere schau mal nach "dove tailing" wenns dich interessiert. Smile
Knusperkekse
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 25.09.2007
Beiträge: 57

BeitragVerfasst am: 23 Jan 2008 - 15:40:25    Titel:

ähm, das klingt jetzt irgendwie verwirrend ... Confused
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 23 Jan 2008 - 15:41:03    Titel:

Masor hat folgendes geschrieben:
Der allgemeine Beweis semi-entscheidbar <=> rekursiv aufzählbar ist aber nur in die eine Richtung trivial, für die andere schau mal nach "dove tailing" wenns dich interessiert. Smile


Der Beweis wird hier gerade gar nicht gesucht...

Cyrix
Knusperkekse
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 25.09.2007
Beiträge: 57

BeitragVerfasst am: 23 Jan 2008 - 15:43:04    Titel:

cyrix42 hat folgendes geschrieben:

Der Beweis wird hier gerade gar nicht gesucht...


Nicht, was beweise ich dann? Dann hab ich den Satz wohl falsch verstanden?
Masor
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 16.07.2006
Beiträge: 256

BeitragVerfasst am: 23 Jan 2008 - 15:52:24    Titel:

Hab ja auch nicht geschrieben, dass er gebraucht wird. Aber da er im Eingangspost erwähnt wurde, bestand ja vielleicht Interesse. Rolling Eyes
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 23 Jan 2008 - 15:54:53    Titel:

Ist aj auch kein Problem, nur die Fragestellung ist wesentlich trivialer...

Cyrix
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Beweis (semi-entscheidbar <=> rekursiv aufzählbar)
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2  Weiter
Seite 1 von 2

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum