Was ist der Unterschied zwischen rekursiven und rekursiv aufzählbaren Sprachen
Ich Frage mich, was der Unterschied zwischen rekursiven und rekursiv aufzählbaren Sprachen ist im Hinblick auf die Eindämmung und Turing-Maschinen. Ich weiß, dass die rekursiv aufzählbaren Sprachen sind eine Teilmenge der rekursiven Sprachen, aber ich bin mir nicht sicher über den Unterschied darüber hinaus.
- Könnte besser geeignet sein für cstheory.stackexchange.com oder cs.stackexchange.com
- Ich werde die Abstimmung zu schließen, ist diese Frage off-topic, weil es um die Theorie der Berechnung, nicht die Programmierung.
- Ich denke, die Tatsache, dass es "Theorie" und "Berechnung-Theorie" tags rechtfertigt meine Frage.
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Haben Sie die Beziehung zwischen R und RE rückwärts: R ist eine (richtige) Teilmenge von RE. Im Grunde genommen ist eine rekursive Sprache ist, für die Sie insgesamt Entscheider.
Erinnern Sie sich an eine definition von rekursiv aufzählbaren Sprachen, für die ein teilweise Entscheidungsspiel vorhanden ist; das ist, eine Turing-Maschine, die, da als Eingabe ein Wort über Ihre alphabet, entweder richtig akzeptieren/ablehnen das Wort nach Ihrer Sprache, oder wenn das Wort nicht in Ihrer Sprache, es kann eine unendliche Schleife.
Einer rekursiven Sprache, im Gegensatz, ist ein insgesamt Entscheider existiert, also eine, die nie-Schleife, und immer halt in entweder eine Annahme oder eine Ablehnung Zustand.
Setzt man diese zwei Begriffe neben einander, es ist offensichtlich, dass eine rekursive Sprache ist auch rekursiv aufzählbar, da die Gesamt-Entscheidung ist auch eine partielle (es wird einfach nie "wählt", um eine Schleife statt des Stopps mit einer korrekten Antwort).
Der Hauptunterschied ist, dass in der rekursiv aufzählbaren Sprache die Maschine hält für Eingabe-strings, die in der Sprache L. aber für Eingabe-strings, die nicht in L ist, kann es halt oder nicht halt.
Wenn wir kommen, um rekursive Sprache ist es halt immer, ob es akzeptiert wird von der Maschine ist oder nicht. wenn es akzeptiert wird, erreicht er bei (q annehmen) und halt. und wenn nicht akzeptiert, durch die Maschine direkt erreichen (q halt).