I have doubts regarding a proof of the following theorem:
'Set of all problems' is larger than the 'set of all algorithms' (or set of all C programs).
Put rhetorically, the theorem says that there are more problems than there are solutions.
The proof is by cardinality comparison of the two sets and has the following steps.
- (Lemma 1) Prove that the 'set of all C programs' is at most countable.
- (Lemma 2) Prove that the 'set of all problems' is at least uncountable.
- Hence, $|$set of all problems$| > |$set of all C programs$|$ ($|.|$ represents cardinality)
For completion, and to ensure that we all are on the same page, I have stated the proof below. However, my concern is not related to the proof directly.
Proof of Lemma 1
The vocabulary of C language is finite (say of size $K$). Therefore, every text of finite length written in C can be encoded as a number in base $K$. Hence, the set of all finite-length texts written in C is of the same cardinality as the set of all numbers in base $K$ i.e. countable. The set of all syntactically and semantically valid C programs is only a subset of this set, hence that set is at most countable.
Proof of Lemma 2
Consider the following set: $S = \{f\ |\ f$ is a function from $\mathbb{N}$ to $\{0,1\}\}$. Now, we shall find the cardinality of $S$. To that end, map each function $f$ in $S$ to a unique subset $T_f$ of $\mathbb{N}$ s.t. $f(x)=1$ iff $x$ is in the subset $T_f$. This mapping is a bijection and hence the cardinality of set $S$ is same as the cardinality of the set of all $T_f$s i.e. the power set of $\mathbb{N}$ i.e. uncountable.
Then we agree/realize/assume that set $S$ is a subset of the set of all problems and hence the latter set is at least uncountable, which completes the proof.
I cannot see $S$ as being a subset of all problems. Why is every element of $S$ a problem in itself? Is it not more sane to talk only about the problems that you can understand and communicate (in English say)?
To me, any problem must be explainable in English, for it to be called a problem. It is not meaningful to be talking about other problems anyway. Therefore, the set of all (worthy) problems must at most be countable, since the set $E$ of all English texts of finite length is countable (proved like Lemma 1 above). So, if we assume that we can write each individual element of $S$ as a problem, that leads us to conclude that all problems in $S$ are elements of $E$, and therefore $|E| \geq |S|$ which is clearly false (since $S$ is uncountable).
Therefore, we cannot even write individual problems of $S$ in English, let alone the whole set. Why are we concerned about those problems then? $S$ may represent one set of decision problems, but are these decision problems worth solving? Should we just believe that there are uncountably many problems even if we would never want to solve uncountably many of them?
I do understand that the notion of a problem for me (the explainability in English) is different from the one that the proof uses. That is fair and in theory I can see why that might be appreciated as well. But this theorem and the corresponding proof limit all human efforts. They tell us that no matter what we do, we will never be able to get all the questions (forget about the answers). So, I want to be really sure that there is indeed no hope. Sorry for being sentimental about this but it is one of those things which render me powerless. It is right up there with Gödel's Incompleteness Theorems, results that forever limit our abilities and make us doubt our entire existence.
Please help me understand why is $S$ a set of problems worth considering and what is a problem after all? Thanks for your time!
