decidability of $\{x|W_x \text{is different from K in only finitely many elements}\}$

Question

Is the following language decidable? Please explain your argument as I want to learn how such problems must be solved to do the rest on my own.

$$\{x \mid W_x \text{ is different from K in only finitely many elements}\},$$ where $W_x = \text{dom}(\Phi_x)$ and $K=\{x \mid \Phi_x(x) \downarrow\}$.

Answer 1

The usual way of proving something is not computable, not c.e., etc, it to reduce a problem known to be not computable, not c.e., etc to it. In this case, the details are as follows:

Let $A$ denote the set you are interested in.

Let $\bar{K}$ denote the complement of $K$. Define a partial computable function $\Psi$ as follows:

$\Psi(x,y) = \begin{cases} 0 & \quad \text{if }\Phi_{x,y}(x) \uparrow \wedge \Phi_y(y) \downarrow \\ \uparrow & \quad \text{otherwise} \end{cases}$

where the function $\Phi_{x,y}(x)$ is defined to converges if and only if $\Phi_x(x)$ has converged by stage $y$. Intuitively, this algorithm runs $\Phi_x(x)$. For each $y$, if it has not converged yet at stage $y$, then run $\Phi_y(y)$, outputting $0$ if $\Phi_y(y)$ converges and leaving it undefined if it never halts. This is clearly partial computable. By the s-m-n theorem, there is a computable function $f$ such that

$\Psi(x,y) = \Phi_{f(x)}(y)$

If $x \in \bar{K}$, then for all $y$, $\Phi_{x,y}(x) \uparrow$. Hence $\Phi_{f(x)}(y) = \Psi(x,y)$ halts if and only if $y \in K$. So $W_{f(x)} = K$ So $f(x) \in A$.

Suppose $x \notin \bar{K}$. That is $x \in K$. So $\Phi_x(x) \downarrow$. Let $s$ be the least stage such that $\Phi_{x,s}(x) \downarrow$. Then $\Phi_{f(x)}(y)$ converges only for those $y \in K$ and $y < s$. So $W_{f(x)}$ is actually finite. $K$ is clearly infinite, so $f(x) \notin A$.

So this $f$ is the many to one reduction of $\bar{K} \leq_m A$. $K$ is not computable so $\bar{K}$ is not computable. So $A$ is not computable.

Answer 2

In your case you can apply Rice's Theorem.

The set you consider denotes a set of functions with a nontrivial property, so the conditions of Rice's theorem hols. If you are interested in a more elementary proof, you can carry out the (very simple) construction in the proof of Rice's Theorem. This will give you reduction to the halting problem.