A Function That Is Not Computable
Pick any programming language as powerful as Turing machines. Enumerate all possible programs, inputs and outputs. Let P(n) be the output of the nth program and the nth input. Let F(x) equal P(x) + 1 or 0, depending on whether P(x) exists. If F was computable, it would equal the kth program for some k. That would imply F(k) = F(k) + 1 which is impossible.
Comments
Post a Comment