1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! Your proof is similar to the proof shown in the Cutland's book. $\endgroup$ – Carlos Feb 15 '19 at 10:38
  • $\begingroup$ I have rectified a statement in my proof and i think that the proof is now correct: We assume that f(x) is a PARTIAL computable function $\endgroup$ – Carlos Feb 15 '19 at 10:51
  • 1
    $\begingroup$ @Carlos Your updated proof still doesn't work. You should think carefully through both cases and study the proof that I've suggested: As far as I can see, there's no way to derive a contradiction directly from $f$ -- you need some other partially computable function that wraps $f$ into a diagonal argument like I did. $\endgroup$ – Stefan Mesken Feb 15 '19 at 10:56

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.