Gibt es ein Beispiel für eine rekursive Sprache, die nicht kontextsensitiv ist?

Ich habe nach einer prototypischen Sprache für rekursive Sprachen (entscheidbar) gesucht, die ohne Erfolg nicht kontextsensitiv ist. Zum Beispiel ist ein Prototyp für reguläre Sprachen, für kontextfreie Sprachen und für kontextsensitive Sprachen. Normalerweise betrachte ich die Sprache, die von einer universellen Turing-Maschine (UTM) akzeptiert wird, als prototypisch oder rekursiv aufzählbar. Für die rekursiven Sprachen habe ich jedoch keine. Früher dachte ich, dass war rekursiv, aber die Überprüfung, ob eine Zahl prime ist, kann von einer begrenzten Turing-Maschine durchgeführt werden. Ich hatte auch aber ich überprüfe erneut, ob dies von einer begrenzten Turing-Maschine durchgeführt werden kann.$a^*$$a^nb^n$$a^nb^nc^n$$\{1^p | p \text { is prime}\}$$\{1^{2^{n}}\}$

Andererseits sind die anderen Optionen, die ich gefunden habe, das Berechnen von Turing-Maschinen, die erfordern, dass die Ausgabe der Berechnung irgendwo in der Maschine gespeichert wird. Die Ausgabe ist jedoch kein Teil der akzeptierten Sprache, die jede dieser Sprachen regulär oder kontextbezogen macht soweit frei. Zum Beispiel die Maschine, die zwei durch 1s dargestellte und durch ein Leerzeichen getrennte Zahlen summiert und das Ergebnis danach setzt. In diesem Fall ist die akzeptierte Sprache tatsächlich was regulär ist! Wenn wir versuchen, es wie eine Überprüfung zu tun, wenn es kontextfrei wird aber nicht rekursiv!$1^*B1^*$$1^nB1^mB1^{n+m}$

Ist es also möglich, über eine rekursive Sprache zu sprechen, die im Wesentlichen regelmäßig ist, aber da sie dazu konditioniert ist, die Berechnung durchzuführen und ein Ergebnis in die Ausgabe als eine Art rekursive Sprache einzufügen? Diese können definitiv nicht in einer begrenzten Turing-Maschine durchgeführt werden.

Hier ist ein formellerer Beweis nach dem Standardtrick der Diagonalisierung (es muss Folklore sein, aber ich habe ihn kürzlich hier gesehen )

Sei eine Aufzählung kontextsensitiver Grammatiken (überzeugen Sie sich davon, dass es nur viele davon gibt; warum können sie aufgezählt werden?),$G_1, G_2, ...$

Sei die Aufzählung von (dh , , , usw. im Fall des binären Alphabets).$x_1, x_2, \ldots,$$\Sigma^*$$x_1=\epsilon$$x_2=0$$x_3=1$$x_4=00$

Betrachten Sie die Sprache:

Anspruch 1 ist nicht kontextsensitiv: Wenn dies der war, wurde es von einem bestimmten generiert, aber während .$L$$G_j$$x_j\in L$$x_j \notin G_j$

Anspruch 2 ist entscheidbar: Wenn gegeben ist, prüfen wir nur, ob erzeugt (dieses Problem ist bekanntermaßen PSPACE-vollständig und somit entscheidbar).$L$$x_i$$G_i$