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

  • 3
    $\begingroup$ What part of the argument don't you understand? $\endgroup$ – Yuval Filmus Jan 17 '14 at 18:55
  • 3
    $\begingroup$ There is a good explanation at our reference question. $\endgroup$ – Raphael Jan 17 '14 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$ – David Richerby Jan 17 '14 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$ – Andrej Bauer Jan 17 '14 at 23:14

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

  • $\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 Jan 18 '14 at 8:17

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.