<p>it's not in RE, you can show it by reduction from $\bar{HP}$. It's one of the common reductions (at least in the course i taught) but it's kind of tricky to figure out if you haven't seen it.</p>

<p>(added following the comments): consider the following reduction from $\bar{HP}$: $f(M,x)=M_{x}$ where $M_{x}$ acts in the following manner on an input w:</p>

<ul>
<li>run M on x for |w| steps</li>
<li>if M stops then reject w</li>
<li>else accept</li>
</ul>

<p>if $(M,x)\in \bar{HP} $  then $L(M_{x})=\Sigma ^{*} $, if $(M,x)\notin \bar{HP} $  then $L(M_{x}) $ is finite and therefore in R.  This is still not sufficient to answer the original question, to do that you must refine the reduction a bit, so that instead of $\Sigma^{*}$ you get a language that HP is reducible to (for instance, HP itself).</p>

CC BY-SA 2.5
2010-09-02T00:04:29.650Z
Could you elaborate?
Emil
CC BY-SA 2.5
2010-09-02T02:20:43.497Z
Yes please. I considered that but wasn't successful in figuring out one.
EpsilonVector
CC BY-SA 2.5
2010-09-02T16:45:46.070Z
OK thanks I got the idea... Although I think you made a mistake in your conclusion of the reduction: if $(M,x)\in \bar{HP} $ then for every input w M will not halt on x and therefore we will reject, making the language of M_{x} an empty set. Or am I missing something?
EpsilonVector
CC BY-SA 2.5
2010-09-02T18:40:45.353Z
there was a mistake in what i wrote, now corrected
yohay kaplan
CC BY-SA 2.5
2010-09-18T08:24:24.203Z
The problem is that showing that $\bar{HP}$ reduces to a language $L$ does not prove that $L$ is not r.e. (indeed $L$ could be HP itself)
LaurentBienvenu
CC BY-SA 2.5
2010-09-01T22:48:31.510Z
2010-09-02T18:40:19.130Z
2010-09-02T18:40:19.130Z
yohay kaplan
<p>One can solve this problem either by a direct proof or using an extended version of Rice's theorem (Theorem II.4.2 in Oddifredi's book <em>Classical Recursion Theory I</em>, where it is attributed to Myhill, Sheperdson, McNaughton and Shapiro). I'll start by the latter.</p>

<p>Rice's theorem says that given a property $P$ of languages:</p>

<ul>
<li>either $P$ is trivial (i.e. either all languages satisfy $P$, or none does)</li>
<li>or the set $\mathcal{A}$ = {$M$ | $L(M)$ has the property $P$} is not computable </li>
</ul>

<p>But here we want to know whether $\mathcal{A}$ can be recursively enumerable (the current trend is to say "computably enumerable" instead). This can happen: take for example: {$M$ | $M$ halts on at least 7 inputs}</p>

<p>The generalized version of Rice's theorem says the following. Given a property $P$ of languages, the set $\mathcal{A}$ = {$M$ | $L(M)$ has the property $P$} is computably enumerable if and only if there exists a computably enumerable set $F$ of finite sets of strings such that: $M \in L \Leftrightarrow (\exists u \text{ finite})~[u \in F  \text{  and  }  u \subseteq L(M)]$.</p>

<p>(Notice that it makes sense to talk about a computably enumerable set of <em>finite sets of strings</em>, as such objects can themselves be encoded by strings).</p>

<p>Here we have the set $\mathcal{A}$ = {$M$ | $HP$ reduces to $L(M)$}. Suppose $\mathcal{A}$ is finite. Then there exists a computably enumerable set $F$ as above. Now</p>

<ul>
<li>If $F$ is non-empty and contains a finite set of strings $u$, then let $M_u$ be a Turing machine whose domain $L(M_u)$ is exactly $u$ (this is easy to build). Then by definition of $F$, $M_u \in \mathcal{A}$, but this means that $HP$ reduces to $L(M_u)=u$, which is a finite set (hence computable), a contradiction since $HP$ is not computable.</li>
<li>Or $F$ is empty, in which case $\mathcal{A}$ is also empty, but this is not the case as there <strong>does</strong> exist a machine $M_{HP}$ whose domain is exactly $HP$ (as $HP$ is computably enumerable). </li>
</ul>

<p>We have a contradiction!</p>

<p>But if you don't like using too powerful theorems we can do this directly, via an adaptation of Yohay's proof. Let $\mathcal{A}$ = {$M$ | $HP$ reduces to $L(M)$}. If $\mathcal{A}$ were computably enumerable, it would reduce to the halting problem $HP$. To show that this is not the case, we will show that some set <strong>harder than $HP$</strong> can be reduced to $\mathcal{A}$. We'll take the following: $INF$ = {$M$ | $L(M)$ is infinite}. The fact that $HP$ reduces to $INF$ but not vice-versa is standard (if you don't believe me, here is a nice and fairly easy exercise for you!).</p>

<p>Now we want to reduce $INF$ to $\mathcal{A}$. Let $M_{HP}$ be a fixed machine such that $L(M_{HP})=HP$. Let $M$ be any machine. Using $M$, construct the machine $M'$ which does the following.</p>

<p>For all input $x$, $M'$ counts the numbers of elements in $L(M)$. Whenever $n$ elements are found in $L(M)$, $M'$ runs the computation of $M_{HP}(x)$ during $n$ steps of computation. If this halts at any point, then $M'$ halts too, if not it waits to find more elements in $L(M)$ and repeats the process. There are two cases:</p>

<ul>
<li>If $M \notin INF$, then calling $k$ the number of elements of $L(M)$, by construction $M'$ will only emulate $M_{HP}$ during $k$ steps of computation for any input. For large inputs (|x|>k), this will be insufficient as $k$ steps won't even be enough to read the input! Hence $M'$ will not halt for all inputs $x$ such that $|x|>k$, hence $L(M')$ is finite, and hence $L(M') \notin HP$</li>
<li>If $M \in INF$, then for any input $x$, $M'$ emulates $M_{HP}$ for infinitely many steps of computation, hence $L(M')=L(M_{HP})=HP$. And therefore $M' \in \mathcal{A}$.</li>
</ul>

<p>We have proven $M \in INF \Leftrightarrow M' \in \mathcal{A}$, so $INF$ reduces to $\mathcal{A}$, which is what we wanted. </p>

CC BY-SA 2.5
2010-09-18T09:17:21.083Z
2010-09-18T09:17:21.083Z
LaurentBienvenu
<p>There's a computability theory exercise that had me stuck for a long time. I have the language</p>

<pre><code>L={ M | there exists a reduction from HP to L(M) }
</code></pre>

<p>I managed to prove it's not in R with a reduction from HP, but I can't figure out if it's in RE (or rather, I suspect it must not be in RE but can't prove it).</p>

<p>I'm not necessarily looking for an actual solution, but a clear enough hint, since it did elude me for a while now.</p>

<p>EDIT: M is a Turing machine. L(M)={x | M accepts x}. HP is the Halting Problem. RE is the Recursively Enumerable class of languages. </p>

CC BY-SA 2.5
2010-09-01T22:18:48.980Z
HP ? Halting problem ?
Suresh Venkat
CC BY-SA 2.5
2010-09-01T22:31:13.557Z
I do not know much about computability theory, but here is what I tried (assuming HP stands for the halting problem): if some language not in RE is many-one reducible to L, we are done.  What is a typical example of a language not in RE?  If I am not mistaken, this will give you an answer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-02T00:09:24.643Z
I believe posters should not use acronyms without defining them! And that includes RE, which not everyone will be familiar with. Also, I guess M a Turing machine and L(M) the language it accepts?
Emil
CC BY-SA 2.5
2010-09-02T07:59:33.653Z
Homework question?
Kaveh
CC BY-SA 2.5
2010-09-02T09:57:44.767Z
Homework or not, it's been posted now and other people are interested in the answer.
Emil
<computability>
Is the following language in RE?
EpsilonVector
# Is the following language in RE?

(Asked by: username_0 on 2010-09-01)

There's a computability theory exercise that had me stuck for a long time. I have the language
L={ M | there exists a reduction from HP to L(M) }

I managed to prove it's not in R with a reduction from HP, but I can't figure out if it's in RE (or rather, I suspect it must not be in RE but can't prove it).
I'm not necessarily looking for an actual solution, but a clear enough hint, since it did elude me for a while now.
EDIT: M is a Turing machine. L(M)={x | M accepts x}. HP is the Halting Problem. RE is the Recursively Enumerable class of languages.

**Tags:** computability

> **Comments:**
> **username_1**: HP ? Halting problem ?  
> **username_2**: I do not know much about computability theory, but here is what I tried (assuming HP stands for the halting problem): if some language not in RE is many-one reducible to L, we are done.  What is a typical example of a language not in RE?  If I am not mistaken, this will give you an answer.  
> **username_3**: I believe posters should not use acronyms without defining them! And that includes RE, which not everyone will be familiar with. Also, I guess M a Turing machine and L(M) the language it accepts?  
> **username_4**: Homework question?  
> **username_3**: Homework or not, it's been posted now and other people are interested in the answer.  

---

## 2 answers

### Answer by username_5 on 2010-09-01. Score: 4 | Accepted answer

it's not in RE, you can show it by reduction from $\bar{HP}$. It's one of the common reductions (at least in the course i taught) but it's kind of tricky to figure out if you haven't seen it.

(added following the comments): consider the following reduction from $\bar{HP}$: $f(M,x)=M\_{x}$ where $M\_{x}$ acts in the following manner on an input w:

* run M on x for |w| steps
* if M stops then reject w
* else accept

if $(M,x)\in \bar{HP} $ then $L(M\_{x})=\Sigma ^{\*} $, if $(M,x)\notin \bar{HP} $ then $L(M\_{x}) $ is finite and therefore in R. This is still not sufficient to answer the original question, to do that you must refine the reduction a bit, so that instead of $\Sigma^{\*}$ you get a language that HP is reducible to (for instance, HP itself).

> **Comments:**
> **username_3**: Could you elaborate?  
> **username_0**: Yes please. I considered that but wasn't successful in figuring out one.  
> **username_0**: OK thanks I got the idea... Although I think you made a mistake in your conclusion of the reduction: if $(M,x)\in \bar{HP} $ then for every input w M will not halt on x and therefore we will reject, making the language of M_{x} an empty set. Or am I missing something?  
> **username_5**: there was a mistake in what i wrote, now corrected  
> **username_6**: The problem is that showing that $\bar{HP}$ reduces to a language $L$ does not prove that $L$ is not r.e. (indeed $L$ could be HP itself)  

---

### Answer by username_6 on 2010-09-18. Score: 8

One can solve this problem either by a direct proof or using an extended version of Rice's theorem (Theorem II.4.2 in Oddifredi's book *Classical Recursion Theory I*, where it is attributed to Myhill, Sheperdson, McNaughton and Shapiro). I'll start by the latter.

Rice's theorem says that given a property $P$ of languages:

* either $P$ is trivial (i.e. either all languages satisfy $P$, or none does)
* or the set $\mathcal{A}$ = {$M$ | $L(M)$ has the property $P$} is not computable

But here we want to know whether $\mathcal{A}$ can be recursively enumerable (the current trend is to say "computably enumerable" instead). This can happen: take for example: {$M$ | $M$ halts on at least 7 inputs}

The generalized version of Rice's theorem says the following. Given a property $P$ of languages, the set $\mathcal{A}$ = {$M$ | $L(M)$ has the property $P$} is computably enumerable if and only if there exists a computably enumerable set $F$ of finite sets of strings such that: $M \in L \Leftrightarrow (\exists u \text{ finite})~[u \in F \text{ and } u \subseteq L(M)]$.

(Notice that it makes sense to talk about a computably enumerable set of *finite sets of strings*, as such objects can themselves be encoded by strings).

Here we have the set $\mathcal{A}$ = {$M$ | $HP$ reduces to $L(M)$}. Suppose $\mathcal{A}$ is finite. Then there exists a computably enumerable set $F$ as above. Now

* If $F$ is non-empty and contains a finite set of strings $u$, then let $M\_u$ be a Turing machine whose domain $L(M\_u)$ is exactly $u$ (this is easy to build). Then by definition of $F$, $M\_u \in \mathcal{A}$, but this means that $HP$ reduces to $L(M\_u)=u$, which is a finite set (hence computable), a contradiction since $HP$ is not computable.
* Or $F$ is empty, in which case $\mathcal{A}$ is also empty, but this is not the case as there **does** exist a machine $M\_{HP}$ whose domain is exactly $HP$ (as $HP$ is computably enumerable).

We have a contradiction!

But if you don't like using too powerful theorems we can do this directly, via an adaptation of Yohay's proof. Let $\mathcal{A}$ = {$M$ | $HP$ reduces to $L(M)$}. If $\mathcal{A}$ were computably enumerable, it would reduce to the halting problem $HP$. To show that this is not the case, we will show that some set **harder than $HP$** can be reduced to $\mathcal{A}$. We'll take the following: $INF$ = {$M$ | $L(M)$ is infinite}. The fact that $HP$ reduces to $INF$ but not vice-versa is standard (if you don't believe me, here is a nice and fairly easy exercise for you!).

Now we want to reduce $INF$ to $\mathcal{A}$. Let $M\_{HP}$ be a fixed machine such that $L(M\_{HP})=HP$. Let $M$ be any machine. Using $M$, construct the machine $M'$ which does the following.

For all input $x$, $M'$ counts the numbers of elements in $L(M)$. Whenever $n$ elements are found in $L(M)$, $M'$ runs the computation of $M\_{HP}(x)$ during $n$ steps of computation. If this halts at any point, then $M'$ halts too, if not it waits to find more elements in $L(M)$ and repeats the process. There are two cases:

* If $M \notin INF$, then calling $k$ the number of elements of $L(M)$, by construction $M'$ will only emulate $M\_{HP}$ during $k$ steps of computation for any input. For large inputs (|x|>k), this will be insufficient as $k$ steps won't even be enough to read the input! Hence $M'$ will not halt for all inputs $x$ such that $|x|>k$, hence $L(M')$ is finite, and hence $L(M') \notin HP$
* If $M \in INF$, then for any input $x$, $M'$ emulates $M\_{HP}$ for infinitely many steps of computation, hence $L(M')=L(M\_{HP})=HP$. And therefore $M' \in \mathcal{A}$.

We have proven $M \in INF \Leftrightarrow M' \in \mathcal{A}$, so $INF$ reduces to $\mathcal{A}$, which is what we wanted.


---

