4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your reasoning is faulty. You argue why one algorithm can not work, but you conclude that no algorithm can work. $\endgroup$ – Raphael Jan 18 '14 at 20:26
  • $\begingroup$ @Raphael How so? $\endgroup$ – PALEN Jan 19 '14 at 16:15
  • $\begingroup$ It's your statement "we would check equality for infinite inputs" -- a recognizer does not need to do this (as it's clearly impossible). For instance, it may inspect the "program" (i.e. the index) and decide on that basis. (That this can not work here is a non-trivial result, cf. Rice's theorem.) $\endgroup$ – Raphael Jan 19 '14 at 16:18
3
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there any question you have about this approach? I've posted two reductions recently, so I appreciate that you are applying that, but SE is not really the place for feedback on your learning. $\endgroup$ – Raphael Jan 18 '14 at 20:27
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\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.