… Uncomputable problems?

So in my lecture today, while speaking about infinities, we encountered a nice litte “proof” of why there have to be some uncomputable problems. Intuitively, many would probably guess (me as well, would I not have heard about it before) that we can most certainly compute any problem on a computer. I mean, programming and our machines have come a long way. But some of us know better and are aware that there are in fact functions that we will never be able to express in programming, no matter how sophisticated the approach. When coming from the mathematical side, this can be illustrated (and proven, however I will only sketch it here) quite short and nicely.

Let’s crunch some numbers

So the first fact to establish is, what functions we are talking about: functions \(f: \mathbb{N} \rightarrow \mathbb{N}\). Obviously, we can say we are talking about the set of all functions from the naturals into the naturals \(\mathbb{N}^{\mathbb{N}}\). Next to consider is the powerset \(\mathcal{P}(\mathbb{N})\). We know (and if we think about it, it’s intuitive: a subset of a set can be represented by a 0 for all elements not included and a 1 for all included elements from the original set) that the powerset is actually the set of all functions \(\{0, 1\}^{\mathbb{N}}\). This set is obviously a subset of all functions of \(\mathbb{N}^{\mathbb{N}}\), since \(0\) and \(1\) are natural numbers: \(\{0, 1\}^{\mathbb{N}} \subseteq \mathbb{N}^{\mathbb{N}}\). The last puzzle piece, before we have the entire picture is that we need to be aware of the fact that a set is always strictly smaller then its powerset (intuitively clear, proof is also short, even though I will skip it here): \(\vert\mathbb{N}\vert < \vert\mathcal{P}(\mathbb{N})\vert\). We can now connect this fact to our previous ideas: \(\vert\mathcal{P}(\mathbb{N})\vert = \vert\{0, 1\}^{\mathbb{N}}\vert\) and further \(\vert\{0, 1\}^{\mathbb{N}}\vert \leq \vert\mathbb{N}^{\mathbb{N}}\vert\).

Proof by simple counting

The full equation is \(\vert\mathbb{N}\vert < \vert\mathcal{P}(\mathbb{N})\vert = \vert\{0, 1\}^{\mathbb{N}}\vert \leq \vert\mathbb{N}^{\mathbb{N}}\vert\) and so by transitivity \(\vert\mathbb{N}\vert < \vert\mathbb{N}^{\mathbb{N}}\vert\). We are finished! But why? Actually, the natural numbers are countably infinite and so are the number of all possible imaginable computer programs. A computer programm is just a finite sequence of 0s and 1s and it can easily be seen that there are countably infinitely many of them. So \(\vert\mathbb{N}\vert\) is actually the number of all possible programs. And, as explained earlier, the number of all possible functions is \(\vert\mathbb{N}^{\mathbb{N}}\vert\). By showing that there are strictly more functions possible than computer programs, there have to be some functions that can not be expressed with a computer program. Simply because of the sheer numbers.

I found this approach quite neat and understandable and I hope you can also find some enjoyment in it! If you have any remarks or have a question about the proof you are very welcome to send me a message and I can try to explain further or clear your doubts! Thanks for reading!