8
$\begingroup$

I am familiar with the theorem which states that some languages are not in the RE (Recursively Enumerable) class of languages, but that can mean either that they are all in CO-RE (or rather, the part of it that doesn't intersect with RE), or that they are partly in CO-RE and partly somewhere else.

Are there languages about which nothing can be decided, not even what words are not in them?

$\endgroup$

3 Answers 3

26
$\begingroup$

Yes, there are some. There is actually an infinite hierarchy of languages which are less and less decidable, namely the Arithmetical hierarchy. Recursively Enumerable languages and their complements are at its level 1. An example of language which isn't RE or coRE is the set of Turing machines computing total functions.

$\endgroup$
11
$\begingroup$

To complement Michael Blondin’s nice answer, actually there are many languages which are not in RE or in coRE or even in the arithmetic hierarchy in the following sense: there are ℵ languages, but there are only ℵ0 languages in the arithmetic hierarchy!

$\endgroup$
10
  • 4
    $\begingroup$ {<M, i> : L(M) is in level i of the arithmetic hierarchy} being such a language $\endgroup$ Nov 19, 2010 at 23:12
  • $\begingroup$ @Michael: I do not think that I know enough about the computability theory to understand your comment. How is your M encoded? $\endgroup$ Nov 19, 2010 at 23:29
  • $\begingroup$ I was giving an example of a language which isn't in the hierarchy. Given the description of a Turing machine M and a natural number i, the problem of determining whether the language of M is in the level i (but not i+1) of the arithmetic hierarchy isn't in the arithmetic hierarchy, otherwise we'd get a contradiction. $\endgroup$ Nov 20, 2010 at 0:41
  • $\begingroup$ @Michael: I still cannot understand. If M is a Turing machine, I think that L(M) is necessarily in RE by the definition of RE. $\endgroup$ Nov 20, 2010 at 2:05
  • 1
    $\begingroup$ Michael's first example can be defined as $\{$ $(\varphi,k): \varphi $ is an arithmetical (i.e. first-order arithmetic) formula expressible using only k quantifier alternations $\}$. A simpler set would be $\{$ $(\varphi(x),n) : \varphi(x)$ is an arithmetical (i.e. first-order arithmetic) formula and $\varphi(n)$ is true $\}$. $\endgroup$
    – Kaveh
    Nov 20, 2010 at 9:30
4
$\begingroup$

Michael and Tsuyoshi's answers are great, but I'm surprised that no one was precise about just how many languages are not in the first level of the arithmetic hierarchy. Michael said that "some" and Tsuyoshi said that "many" languages are in neither RE nor co-RE. In fact (as Tsuyoshi implicitly put in his answer) almost every language is in neither RE nor co-RE. This essentially comes from the fact that there are $2^{\aleph_0}$ languages and only $\aleph_0$ Turing machines.

$\endgroup$
1
  • $\begingroup$ That is what I meant in my answer, but thanks for pointing out the correct term to use! $\endgroup$ Nov 23, 2010 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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