How do we know that there is a function from $\mathbb{N}$ to $\mathbb{N}$ that is not partial computable?

Question

A partial computable function is also known as effectively computable, and is defined as any function that can be computed by a Turing machine with $Dom(f) \subseteq \Sigma^*$, where $\Sigma^*$ is the Kleene star of the alphabet $\Sigma$ for the Turing machine that satisfies partial computability.

How do we know that there exists a function from $\mathbb{N}$ to $\mathbb{N}$ that is not partial computable?

Answer 1

The counting argument is very beautiful but you should also know Alan Turing's demonstration,

According to set theory every Turing machine either halts or does not halt, so let us encode Turing machines as natural numbers and write a map from them to "1" if they halt and "0" if they do not.

That function $\text{halts} : \mathbb N \to \mathbb N$ cannot be implemented in a Turing machine, if it were then you could also build a Turing machine that uses it as a subroutine for the following

natural liar(natural t) { if(halts(t)) { loop(); } else { return 0; } }

This Turing machine takes a Turing machine encoded as a number and loops if it halts and halts if it loops! When you apply this Turing machine to the number encoding it's self you get a paradox, which contradicts the possibility of the "halts" function being implemented in a Turing machine.

Answer 2

A pure "counting" argument, as in the comments, does the job. But perhaps it is worthwhile to be more explicit.

There are countably many Turing machines, so they may be enumerated as $T_0$, $T_1$, $T_2$, and so on.

Let $f(e,x)=0$ if the Turing machine $T_e$ does not halt on numerical input $x$, and let $f(e,x)$ be $1$ more than the result of applying $T_e$ to $x$ otherwise. Finally, let $g(x)=f(x,x)+17$.

We show that $g$ is not Turing computable. For if it is, there is a Turing machine $T_a$ such that $f(a,x)=g(x)$ for all $x$. Put $x=a$. We find that $f(a,a)=g(a)$. But $g(a)=f(a,a)+17$, so $17=0$.

In a way, the above argument is implicit in the "counting" argument, since one shows that the set of functions from $\mathbb{N}$ to $\mathbb{N}$ is uncountable in precisely this way. But it is worthwhile to be explicit, as an easy prelude to more subtle but similar arguments.