Let $f_1,...,f_n$ be an enumeration of all computable functions in N to N. Prove $h(n)=f_n(n)$ is not calculable.

Question

Let $f_1,...,f_n$ be an enumeration of all calculable functions in N to N. Prove $h(n)=f_n(n)$ is not calculable.

I don't really know where to start here, any hint appreciated.

I don't know what is a calculable function, but the argument you want seems to be some kind of Cantor's diagonal argument. — D. Ungaretti, Dec 01 '16 at 17:33

score 2 · Accepted Answer · answered Dec 01 '16 at 17:38

2

Hint : Let us assume $h$ is calculable. Then, so is $1+h$. This means $\exists n_0 \in \mathbb{N}, f_{n_0}=1+h$. What is $h(n_0)$?

answered Dec 01 '16 at 17:38

Vincent

+1. Note for the OP that this breaks down if we allow partial functions, and indeed there are computable enumerations of the computable partial functions. – Noah Schweber Dec 01 '16 at 17:45
Thanks for the insight. If i get it right, we arrive at a contradiction with $h(n_0)=h(n_0)+1$. – Stu-D-ent Dec 01 '16 at 17:47
Noah, by partial functions, do you mean functions computable on a part of $\mathbb{N}$ – Vincent Dec 01 '16 at 17:50

1 Answers1