1
$\begingroup$

For school, we have a proof that some functions are not Turing computable. The example is: $$ G(k) = \begin{cases} f_k(k) + 1 & \text{ if $f_k(k)$ is defined}, \\ 1 & \text{ otherwise}.\end{cases} $$

Claim: $G$ is non computable.

Proof: In view of obtaining a contradiction, let's say $G$ is computable, say by the $k$th Turing machine. Give the encoding of this $k$th Turing machine as an argument for $G$. This leads to a contradiction: if $f_k(k)$ is defined, then $f_k(k)$ is not equal to $g(k) = f_k(k) + 1$. Else $f_k(k)$ is undefined and not equal to $g(k) = 1$.

I don't understand the contradiction, help please...

$\endgroup$
4
  • 3
    $\begingroup$ What part of the argument don't you understand? $\endgroup$ Commented Jan 17, 2014 at 18:55
  • 3
    $\begingroup$ There is a good explanation at our reference question. $\endgroup$
    – Raphael
    Commented Jan 17, 2014 at 21:39
  • 2
    $\begingroup$ If all you want to prove is that there exists an uncomputable function (rather than actually finding one), a simple counting argument suffices: there are countably many Turing machines but uncountably many functions. More details at the question linked by Raphael. $\endgroup$ Commented Jan 17, 2014 at 22:37
  • $\begingroup$ Do you realize that the $k$ in the proof is not the same $k$ as in the definition of $G$? $\endgroup$ Commented Jan 17, 2014 at 23:14

1 Answer 1

5
$\begingroup$

The contradiction reached is that $0 = 1$ which violates one of Peano's axioms. Assume $G$ is computed by the $j$-th Turing machine. Observe that $G$ is everywhere defined. Then $$f_j(j) = G(j) = f_j(j) + 1$$ and by canceling $f_j(j)$ on both sides we get $$0 = 1.$$

$\endgroup$
1
  • $\begingroup$ Thank you! I think I get it now. I guess my teacher put a little too much effort in explaining the matter, which made it more difficult than it is. $\endgroup$
    – voluminat0
    Commented Jan 18, 2014 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.