3
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ HP ? Halting problem ? $\endgroup$ – Suresh Venkat Sep 1 '10 at 22:18
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 1 '10 at 22:31
  • 4
    $\begingroup$ 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? $\endgroup$ – Emil Sep 2 '10 at 0:09
  • $\begingroup$ Homework question? $\endgroup$ – Kaveh Sep 2 '10 at 7:59
  • 1
    $\begingroup$ Homework or not, it's been posted now and other people are interested in the answer. $\endgroup$ – Emil Sep 2 '10 at 9:57
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Could you elaborate? $\endgroup$ – Emil Sep 2 '10 at 0:04
  • $\begingroup$ Yes please. I considered that but wasn't successful in figuring out one. $\endgroup$ – EpsilonVector Sep 2 '10 at 2:20
  • $\begingroup$ 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? $\endgroup$ – EpsilonVector Sep 2 '10 at 16:45
  • $\begingroup$ there was a mistake in what i wrote, now corrected $\endgroup$ – yohay kaplan Sep 2 '10 at 18:40
  • 1
    $\begingroup$ 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) $\endgroup$ – LaurentBienvenu Sep 18 '10 at 8:24
8
$\begingroup$

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.

$\endgroup$

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.