Halteproblem

25.03.2015, 17:35	Auf diesen Beitrag antworten »
Informatikerin12	Halteproblem Hallo :-) Ist die folgende Aussage korrekt? Es gibt eine reguläre Sprache L, sodass HP\L Element aus REC. Die Lösung lautet: Ja. L=Sigma* ist eine reguläre Sprache. Es gilt HP\L=leere Menge Element aus REG, daher gilt insbesondere HP\L Element aus REC. Ich verstehe nicht, wie man jetzt von "HP\L=leere Menge Element aus REG" darauf kommt, dass HP nicht rekursiv bzw. entscheidbar ist. Darf man das einfach so schlussfolgern? LG, Informatikerin12


25.03.2015, 20:49	Auf diesen Beitrag antworten »
Karlito	Hallo Informatikerin12, bitte liefe in Zukunft die Definition der entsprechen Klassen. Leider sind mir nicht alle diese Klassen geläufig, da die theoretische Informatik nich mein Arbeitsgebiet ist. Meine Recherche ergab: REC = {L(M) \| M ist eine DTM, die jede Eingabe entscheidet} Stimmt das soweit? Edit: Meines Verständnisses nach ist REC also die Klasse aller Sprachen, die entscheidbar sind, oder? Demnach ginge es doch darum, ob die leere Sprache ein Element der entscheidbaren Sprachen ist, oder? Gruß, Karlito
25.03.2015, 22:01	Auf diesen Beitrag antworten »
Informatikerin12	Hallo Karlito, die leere Sprache ist ein Element der entscheidbaren Sprachen. Aber warum muss ich hier nicht zeigen, dass HP nicht rekursiv, aber rekursiv-aufzählbar ist? LG, Informatikerin12
26.03.2015, 10:53	Auf diesen Beitrag antworten »
Karlito	Hallo Informatikerin12, Das Halteproblem kann als Sprache aufgefasst werden. Das kommt daher, dass man eine Universelle TM schaffen kann, welche ein Programm vom Band ausließt und dieses dann ausführt. Man wählt üblicherweise dazu die eine Kodierung wie w#x, wobei w die Kodierte spezielle TM ist (also das Programm) und x die Eingabe, welche von dem Programm verarbeitet werden soll. Die Menge aller TM mit allen möglichen Eingaben ergibt dann die Sprache des Halteproblems (so zumindest mein Verständnis). Es handelt sich also Prinzipiell um eine Menge von Wörtern. Nun ist $[latex]\Sigma^[/latex]$ die Menge aller möglichen Wörter über einem Alphabet und es gilt folgende Beziehung $[latex] \mathcal{L} \subseteq \Sigma^[/latex]$ . Das heißt. jede Sprache ist eine Teilmenge von $[latex]\Sigma^[/latex]$ . Im Umkehrschluss gilt für jede Sprache $[latex] \mathcal{L} \backslash \Sigma^ = \emptyset[/latex]$ . Der Nachweis, dass HP nicht rekursiv, aber rekursiv-aufzählbar ist, ist daher nicht notwendig. Soweit klar? Gruß, Karlito
Anzeige

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »