4
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ It's an immediate result by a counting argument (or rather, by showing that the measure of a countable set is 0). $\endgroup$ – Shaull Sep 5 '17 at 9:39
  • 3
    $\begingroup$ 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. $\endgroup$ – Shaull Sep 5 '17 at 12:54
  • 2
    $\begingroup$ 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. $\endgroup$ – Kaveh Sep 5 '17 at 14:37
  • 3
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Sep 5 '17 at 18:46
  • 3
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Sep 5 '17 at 18:55
3
$\begingroup$

So the answer to my original question is the following: Because the statement is a corollary of the two facts that

  1. every program (Turing machine) is a finite binary string, i.e., a natural number,
  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)

the question about the original author / paper of this simple corollary is not that much interesting. (And the origins of the mentioned facts themselves I can trace back, of course.)

EDIT: I add here that this is the answer modulo the objection by Damiano Mazza (see in the comments above), which I need to check/think about first.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.