Ich frage mich, was der Unterschied zwischen rekursiven und rekursiv aufzählbaren Sprachen in Bezug auf Anhalten und Turing-Maschinen ist. Ich weiß, dass rekursiv aufzählbare Sprachen eine Untermenge von rekursiven Sprachen sind, aber ich bin mir nicht sicher über den Unterschied darüber hinaus.Was ist der Unterschied zwischen rekursiven und rekursiv aufzählbaren Sprachen
Sie haben die Beziehung zwischen R und RE rückwärts: R ist eine (richtige) Teilmenge von RE. Im Grunde genommen ist eine rekursive Sprache eine, für die Sie insgesamt entscheiden können.
Rufen Sie eine Definition von rekursiv aufzählbaren Sprachen als eine, für die eine Teilentscheider existiert; das heißt, eine Turing-Maschine, die, wenn Sie ein Wort über Ihr Alphabet eingeben, entweder das Wort entsprechend Ihrer Sprache korrekt annehmen/ablehnen, oder wenn das Wort nicht in Ihrer Sprache ist, kann es für immer eine Schleife bilden. Im Gegensatz dazu ist eine rekursive Sprache eine, für die ein Gesamtentscheider existiert, d. H. Eine, die niemals eine Schleife bildet und immer entweder in einem akzeptierenden oder in einem abweisenden Zustand anhält.
Wenn man diese beiden Definitionen nebeneinander stellt, ist es offensichtlich, dass eine rekursive Sprache auch rekursiv aufzählbar ist, da der gesamte Entscheider auch ein partieller Entscheider ist (er "wählt" nie Schleifen, statt mit einer richtigen Antwort anzuhalten)).
Vielleicht besser für http://cstheory.stackexchange.com oder http://cs.stackexchange.com geeignet – nawfal
Ich stimme diese Frage als off-topic zu schließen, weil es um die Theorie der Berechnung geht, nicht Programmierung. –
@RaymondChen Ich denke, die Tatsache, dass es "Theorie" - und "Computertheorie" -Tags gibt, rechtfertigt meine Frage. – Bren