<p>To complement Michael Blondin’s nice answer, actually there are <em>many</em> 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 ℵ<sub>0</sub> languages in the arithmetic hierarchy!</p>

CC BY-SA 2.5
2010-11-19T23:12:09.040Z
{<M, i> : L(M) is in level i of the arithmetic hierarchy} being such a language
Michael Blondin
CC BY-SA 2.5
2010-11-19T23:29:23.073Z
@Michael: I do not think that I know enough about the computability theory to understand your comment.  How is your M encoded?
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-20T00:41:53.860Z
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.
Michael Blondin
CC BY-SA 2.5
2010-11-20T02:05:40.207Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-20T02:32:37.527Z
@Philip: Then my question would be, to which oracle?
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-20T02:37:55.087Z
@Tsuyoshi, my comment doesn't make any sense. Here is a good language: {<x, i> : x is in the i^th Turing jump of the empty set of the arithmetic hierarchy}.
Michael Blondin
CC BY-SA 2.5
2010-11-20T02:41:51.297Z
@Michael: That seems good.  For those who do not know what the Turing jump is (I did not), see [Wikipedia](http://en.wikipedia.org/wiki/Turing_jump).
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-20T09:30:18.230Z
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 $\}$.
Kaveh
CC BY-SA 2.5
2010-11-19T23:06:04.770Z
2010-11-19T23:06:04.770Z
Tsuyoshi Ito
<p>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) <em>almost every</em> 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.</p>

CC BY-SA 2.5
2010-11-23T19:30:52.370Z
That is what I meant in my answer, but thanks for pointing out the correct term to use!
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-23T09:09:16.083Z
2010-11-23T09:09:16.083Z
Huck Bennett
<p><strong>Yes</strong>, there are some. There is actually an infinite hierarchy of languages which are <em>less and less</em> decidable, namely the <a href="http://en.wikipedia.org/wiki/Arithmetical_hierarchy">Arithmetical hierarchy</a>. 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.</p>

CC BY-SA 2.5
2010-11-19T22:37:12.673Z
2010-11-19T22:53:49.577Z
2010-11-19T22:53:49.577Z
Michael Blondin
<p>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. </p>

<p>Are there languages about which nothing can be decided, not even what words are <em>not</em> in them? </p>

<computability>
Are there languages that are not in RE nor CO-RE?
EpsilonVector
# Are there languages that are not in RE nor CO-RE?

(Asked by: username_0 on 2010-11-19)

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?

**Tags:** computability


---

## 3 answers

### Answer by username_2 on 2010-11-19. Score: 27 | Accepted answer

**Yes**, there are some. There is actually an infinite hierarchy of languages which are *less and less* decidable, namely the [Arithmetical hierarchy](http://en.wikipedia.org/wiki/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.


---

### Answer by username_1 on 2010-11-19. Score: 12

To complement username_2’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!

> **Comments:**
> **username_2**: {<M, i> : L(M) is in level i of the arithmetic hierarchy} being such a language  
> **username_1**: @Michael: I do not think that I know enough about the computability theory to understand your comment.  How is your M encoded?  
> **username_2**: 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.  
> **username_1**: @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.  
> **username_1**: @Philip: Then my question would be, to which oracle?  
> **username_2**: @Tsuyoshi, my comment doesn't make any sense. Here is a good language: {<x, i> : x is in the i^th Turing jump of the empty set of the arithmetic hierarchy}.  
> **username_1**: @Michael: That seems good.  For those who do not know what the Turing jump is (I did not), see [Wikipedia](http://en.wikipedia.org/wiki/Turing_jump).  
> **username_3**: 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 $\}$.  

---

### Answer by username_4 on 2010-11-23. Score: 5

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.

> **Comments:**
> **username_1**: That is what I meant in my answer, but thanks for pointing out the correct term to use!  

---

