Is there an example of a recursive language which is not context sensitive?

Question

I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^*$ is prototypical of regular languages, $a^nb^n$ for context free languages and $a^nb^nc^n$ for context sensitive languages. I usually consider the language which is accepted by a universal Turing machine (UTM) as prototypical of recursively enumerable. However for the the recursive languages I don't have one. I used to think that $\{1^p | p \text { is prime}\}$ was recursive but verifying a number is prime can be done by a bounded Turing machine. I also had $\{1^{2^{n}}\}$ but again verifying this can be done by a bounded Turing machine.

On the other hand, the other options I have found are computing Turing machines that requiere that the output of the computation to be store somewhere in the machine, however the output is no part of the accepted language which makes every of those language regular or context free so far. For instance the machine that sums two numbers represented by 1s and separated by a space, and puts the result after. In this case, the accepted language is actually $1^*B1^*$ which is regular! If we try to do it like verification if become context free $1^nB1^mB1^{n+m}$ but no recursive!

So is it possible to talk about a recursive language which it might be regular in essence but since it is conditioned to do the computation and put a result in the output as a kind of recursive language? Those definitely can not be done in a bounded Turing machine.

Answer 1

Here's a more formal proof, by the standard trick of diagonalization (it must be folklore, but I saw it recently here)

Let $G_1, G_2, ...$ be some enumeration of context sensitive grammars (convince yourself that there are only countable many of them; Why can they be enumerated?),

Let $x_1, x_2, \ldots,$ be enumeration of $\Sigma^*$ (i.e., $x_1=\epsilon$, $x_2=0$, $x_3=1$, $x_4=00$, etc. in the case of binary alphabet).

Consider the language:

$$L = \{ x_i \mid x_i \notin L(G_i)\}.$$

Claim 1 $L$ is not context sensitive: if it was, there was a specific $G_j$ generating it, but $x_j\in L$ while $x_j \notin G_j$.

Claim 2 $L$ is decidable: given $x_i$ we just check if $G_i$ generates it (this problem is known to be PSPACE complete, thus decidable).