World's most popular travel blog for travel bloggers.

[Solved]: Understanding a proof for the existance of a non-computable function

, , No Comments
Problem Detail: 

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

Asked By : Voluminat0

Answered By : Andrej Bauer

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19788

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback