Is the set of programs that compute some function other than $h$ recursively enumerable?

Question

Let $h$ be a total computable function. Is $S = \{x \mid f_x \neq h\}$ recursively enumerable?

Originally this was an exercise that restricted $h$ to: $h(x) = x + 1$ . However, it can be formulated as a more general case.

By Rice's Theorem, it is not recursive. Intuitively,

• $S$ is not r.e. as if it was, it would mean that we would know that $f_x(y)$ halts for some input $y$ in order to check if it has a different image of $h(y)$.

• $\overline{S}$ is not r.e. as if it was, we would be able to check if $f_x(y) = h(y)$ for every input $y$ (we would check equality for infinite inputs).

How would you solve this problem?

Note: I tried something, but I'll post it as an answer. Some thoughts would be great and really helpful. Any approach to this problem using reduction or diagonalization methods would be useful.

Answer 1

The set $S$ is in fact neither c.e. nor co-c.e. You can prove this via an m-reduction to $\overline{TOT} = \{ x | \varphi_x \mbox{ is not total } \}$ (which is also neither c.e. nor co-c.e.).

Define:

$ \varphi_{f(x)}(y)=\begin{cases} h(y) & \mbox{if $\forall z\leq y~\varphi_x(y)$ halts}\\ undefined & \mbox{ow.} \end{cases} $

Where $f$ is from the s-m-n theorem.

Then you have that $\overline{TOT} \leq_m S$ via $f$ because, for all $x$:

$x \in TOT \iff \forall y~\varphi_x(y) \mbox{ is defined} \iff \forall y~\forall z\leq y~\varphi_x(z) \mbox{ is defined} \iff \forall y~\varphi_{f(x)}(y)=h(y) \iff f(x) \notin S$

Answer 2

Suppose $S = \{x | f_x \neq h\}$ is r.e.

Then, define g such that:

$\qquad\displaystyle g(x) = \begin{cases} h(x), &\text{ if $f_{x_0}(x_0)$ halts } \\ undefined, &\text{else} \end{cases} $

Then, $g$ is computable i.e. a $TM$ can be constructed such that it computes $h(x)$ if the $x_0-th$ machine halts on specific input $x_0$ or loops if it does not. Then, $\forall x_0$ $\exists i$ s.t. $f_i = g$. Hence,

$f_i = h \iff f_{x_0}(x_0)$ halts

Let $H = \{x | f_x(x) \text{ halts}\}$. Then, $i \in \overline{S} \iff x_0 \in H$.

Hence, $H \leq_r \overline{S}$, or equivalently, $\overline{H} \leq_r S$.

If $S$ is r.e., $\overline{H}$ is r.e. But $H$ is also r.e. (the Halting Problem is semi-decidable). Consequently, $H$ is recursive which contradicts the fact the the halting problem is undecidable. Hence, $S$ is not r.e.

Answer 3

Let's look at the definition of the set $S = \{ x : f_x \not = h\}$. There are two ways that a given $f_x$ could differ from $h$:

1) For some $n$, $f_x(n) \downarrow \not = h(n)$

2) $f_x(n) \uparrow$ for all $n$.

In the former case, we would be able to find a "witness" $n$ by simulating the execution of $f_x$ on all inputs. But, in the latter case, it seems as if we will never be able to tell, in a finite amount of time, that $f_x$ will never be defined. We can use this insight to show that $S$ is not computable.

Let $A$ be some co-r.e. but not r.e. set, e.g. the complement of the halting problem. Let $h$ be any total computable function, e.g. the constant zero function.

For each $n$, define a function $F(n)$ that does the following. It ignores its input $j$. It just simulates the enumeration of $A^c$. If it finds that $n \in A^c$ then it immediately halts and returns 0 (that is, it returns $h(j)$). Thus $n \in A^c$ if and only if $F(n) = h$; if $n \in A$ then $F(n)(j)$ is undefined for all $j$. Moreover, there is a computable function $p$ that, given $n$, produces an index $p(n)$ for $F(n)$.

Now, for each $n$, $n \in A^c$ if and only if $f_{p(n)} = h$. Thus $n \in A$ if and only if $f_{p(n)} \not = h$, which happens if and only if $p(n) \in S$. If $S$ is an r.e. set then we can enumerate the set of number of the form $p(n)$ that are in $S$, which means we enumerate $A$: if $S$ is r.e. then so is $A$. But that is impossible by the choice of $A$.

This is an example of a sort of "parity switch" argument, which is a useful technique. The proof shows that if $S$ was r.e., we could use that to "switch the parity" of an arbitrary co-r.e. set to r.e. That isn't possible in general, so $S$ can't be r.e. You can see the roots of the parity switch in item (2): $S$ has to "do something" (enumerate $x$) if and only if $f_x$ does not "do something" (halt on at least one input). That sort of situation often lays the foundations for this type of argument.

Answer 4

By the Rice-Shapiro Theorem, S is not c.e. because it is not compact.