3
$\begingroup$

After a lot of searching I came to the conclusion that yes, there are languages that are not even Turing Recognisable, but I can't get good examples which are simple to understand.

Also, I wanna know that what are the properties of a language which is non-Turing Recognisable?

$\endgroup$

1 Answer 1

12
$\begingroup$

I'll answer your questions in order. First, what is a "simple" example of a language which is not Turing recognizable:

If $\mathcal{H}$ is the halting problem, then I claim $\mathcal{H}^c$ (that is, the complement of $\mathcal{H}$) is not recognizable. Why might this be true?


Lemma: For any language $\mathcal{L}$, if $\mathcal{L}$ and $\mathcal{L}^c$ are both recognizable, then actually $\mathcal{L}$ is decidable.

Let $w$ be a word, and fix Turing machines $M$ and $M^c$ for $\mathcal{L}$ and $\mathcal{L}^c$ respectively. If $w \in \mathcal{L}$, then $M(w)$ will halt and accept. If instead $w \not \in \mathcal{L}$, then $M^c(w)$ will halt and accept. Thus, if we run $M$ and $M^c$ in parallel, we know that one of them will halt! Depending on which one it is, we will know if $w \in \mathcal{L}$ or not.


Now, we know that $\mathcal{H}$ is

  • Recognizable
  • Not decidable

Then if $\mathcal{H}^c$ were recognizable, $\mathcal{H}$ would be decidable (by the above lemma) and we contradict.

Concretely, $\mathcal{H}^c = \{ \langle M, x \rangle ~|~ M \text{ codes a Turing machine which _doesn't_ halt on input } x \}$ is not recognizable.


As for what some properties of these languages would be, it becomes harder and harder to say as we move up the complexity hierarchy. Though it might be worth reading about The Arithmetical Hierarchy. We can classify families of languages based on how complicated they are, and there are many results in this area, though they tend to be somewhat cumbersome and abstract.


I hope this helps ^_^

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .