7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Context-sensitive languages are equivalent to languages that can be decided by a linear-bounded Turing Machines. So any language decidable by a general (non LBA) TM, will not be context-sensitive (but rather, can be generated by an unrestricted grammar) $\endgroup$ – Ran G. Apr 28 '16 at 1:20
  • 1
    $\begingroup$ If you want a specific example, think of languages of the form $L=\{ \langle M ,x \rangle \mid M \text{ accepts $x$ within $|x|^{10}$ steps}\}$. $\endgroup$ – Ran G. Apr 28 '16 at 1:22
  • $\begingroup$ Wow, excellent! I got it! This one is always decidable since I only have to simulate M $10$ steps! Thanks a lot! $\endgroup$ – Ivan Meza Apr 28 '16 at 1:31
  • $\begingroup$ Since LINSPACE ≠ R, yes. $\endgroup$ – Raphael Apr 28 '16 at 11:28
6
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ This one is so nice, I have read something like this to establish the relation about complements of family of languages. But using this construction to constrain being outside context sensitive while keeping it recursive is really cool! $\endgroup$ – Ivan Meza Apr 28 '16 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.