7
$\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$
24
$\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.

| cite | improve this answer | |
$\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!

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ {<M, i> : L(M) is in level i of the arithmetic hierarchy} being such a language $\endgroup$ – Michael Blondin Nov 19 '10 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$ – Tsuyoshi Ito Nov 19 '10 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$ – Michael Blondin Nov 20 '10 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$ – Tsuyoshi Ito Nov 20 '10 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 '10 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That is what I meant in my answer, but thanks for pointing out the correct term to use! $\endgroup$ – Tsuyoshi Ito Nov 23 '10 at 19:30

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.