Show that $x \in W_{x}$ is undecidable

223 Views Asked by At

The Cutland's book called Computability has a theorem whose proof i don't understand and i have developed another simpler proof. Could you tell me if this proof is correct?

DEFINITION 1: $\phi_{x}, x \in \mathbb{N}$, is a partial computable function.

DEFINITION 2: $W_{x}$ is de domain of the partial computable function $\phi_{x}$.

THEOREM 1: $x \in W_{x}$ or, equivalently, $\phi_{x}(x)$ is defined, is undecidable.

PROOF: Let f: $\mathbb{N} \rightarrow$ {0, 1} the characteristic function defined as: $$f(x)=\begin{cases} 1 & \text{ if } x \in dom(\phi_{x})\\ 0 & \text{ if } x \notin dom(\phi_{x}) \end{cases}$$

We assume that $f(x)$ is a partial computable function $\Leftrightarrow \exists i \in \mathbb{N}, f = \phi_{i}$

Then,

$$\phi_{i}(x)=f(x)=\begin{cases} 1 & \text{ if } x \in dom(\phi_{x})\\ 0 & \text{ if } x \notin dom(\phi_{x}) \end{cases}$$

If x = i then,

$$\phi_{i}(i)=\begin{cases} 1 & \text{ if } i \in dom(\phi_{i})\\ 0 & \text{ if } i \notin dom(\phi_{i}) \end{cases}$$

But, $\phi_{i}(i)=0$ if $i \notin dom(\phi_{i})$ is a contradiction because $\phi_{i}(i)$ is undefined $\Rightarrow f$ is not computable $\Rightarrow$ The THEOREM 1 is shown.

1

There are 1 best solutions below

3
On

This doesn't work. $\phi_i(i)$ will just be $1$ -- no contradiction here ($\phi_i$ is a total function by assumption).

Instead, consider the following argument:

Let $f$ decide $x \in W_x$. Let $g$ be the partial computational function such that $g$, on input $x$, holds (with value $0$, say) iff and only if $f(x) = 0$. (1)

Let $m < \omega$ be such that $g = \phi_m$. Then $$ m \in W_m \iff \phi_m(m) \text{ holds } \iff f(m) = 0 \iff m \not \in W_m. $$ Contradiction!

(1) Such a $g$ exists: E.g. $g$, on input $x$, will compute $f(x)$. If $f(x) = 0$, it will hold with value $0$. Otherwise, it will go into an infinite loop. (As you can tell, I picture my computable functions as Turing machines.)