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.
