# Original proof that “almost all decision problems are uncomputable”?

Who gave the original proof that "almost all decision problems are uncomputable"? Any hint at the original paper appreciated, thanks!

• It's an immediate result by a counting argument (or rather, by showing that the measure of a countable set is 0). – Shaull Sep 5 '17 at 9:39
• I don't think you'll find the "original". This result would be a trivial corollary of anyone who considers the concept of a decision problem. I guess the original would be the first textbook where it appears. No idea what that might be, though. Very likely not in English, anyway. – Shaull Sep 5 '17 at 12:54
• It is actually an interesting question. The notion of countable and uncountable were already present at the time of Hilbert but he didn't seem to think there can be undecidable problems. It is probably right after the notion of algorithm for formalized in one way or another. Before that one couldn't claim to have a way of describing arbitrary computable sets and therefore enumerate them. – Kaveh Sep 5 '17 at 14:37
• The proof does not require CH, it only needs the uncountability of the reals, the countability of the set of algorithms and the fact that it implies that there is no injection from the reals to a countable set. Also every real $x \in [0,1)$ does encode a meaningful problem: the problem of computing the $i$-th bit in its binary expansion (assuming some convention to distinguish between things like $0.01111\ldots$ and $0.1$). The issue with finding a reference for this is that the proof only makes sense if you formalize "algorithm", which was first done convincingly by Turing. – Sasho Nikolov Sep 5 '17 at 18:46
• Turing's paper mentions that the set of computable numbers is countable, but I can't find a place where he remarks explicitly that this implies the existence of uncomputable numbers: maybe this was too obvious to mention, or maybe he only cared about explicit uncomputable numbers. Instead he observes that if you attempt to prove that the computable numbers are uncountable via diagonalization, you get stuck because of the halting problem. He motivates the proof of the undecidability of the halting problem this way. – Sasho Nikolov Sep 5 '17 at 18:55

2. every decision problem is a function $f: \mathbb{N} \to \{0,1\}$ and hence corresponds to a number $x \in [0,1)$ (and every such $x$ indeed encodes a meaningful decision problem, see Sasho Nikolov's first comment above)