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

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

<p>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.)</p>

<p>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.</p>

CC BY-SA 3.0
2017-09-05T20:13:41.277Z
2017-09-18T08:32:02.487Z
2017-09-18T08:32:02.487Z
InfinitelyInquisitive
<p>Who gave the original proof that "almost all decision problems are uncomputable"? Any hint at the original paper appreciated, thanks!</p>

CC BY-SA 3.0
2017-09-05T09:39:24.850Z
It's an immediate result by a counting argument (or rather, by showing that the measure of a countable set is 0).
Shaull
CC BY-SA 3.0
2017-09-05T11:10:36.887Z
Thank you, Shaull. I am aware of the usual argument, although I only found very few sources. But none of them seems to be the original source or referring to it. The reason that I've asked is that I try to understand basically two things: (1) if the proof uses the CH (I think it is not necessary, although a "quick argument" via 2^N" might use it), and (2) if we can really associate to every infinite bit string a meaningful problem. (2) would be necessary in my opinion to make the argument valid.
InfinitelyInquisitive
CC BY-SA 3.0
2017-09-05T11:10:44.193Z
The usual argument actually not only says/requires that every decision problem can be encoded by an infinite bit string (which is true, of course), but also that every infinite bit string (hence at least every real number x \in [0,1]) encodes a meaningful problem. Otherwise we cannot be sure whether the set of infinite bit strings which encodes meaningful problems is not in fact just a countable subset of all infinite bit strings. (2) seems to be an issue between the syntax and the semantics of (decision) problems.
InfinitelyInquisitive
CC BY-SA 3.0
2017-09-05T11:48:05.177Z
(I should probably add that with "CH" I mean the continuum hypothesis.)
InfinitelyInquisitive
CC BY-SA 3.0
2017-09-05T12:54:00.240Z
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
CC BY-SA 3.0
2017-09-05T14:37:13.223Z
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
CC BY-SA 3.0
2017-09-05T15:27:06.873Z
I wouldn't be surprised if it's even mentioned in Turing's or Church's original paper.
Joshua Grochow
CC BY-SA 3.0
2017-09-05T18:46:34.550Z
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
CC BY-SA 3.0
2017-09-05T18:55:27.483Z
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
CC BY-SA 3.0
2017-09-05T19:48:52.940Z
Thanks Sasho! It was exactly your argument about the converse which I didn't see. Now that it is clear to me that also every $x \in [0,1)$ does encode a meaningful problem, I agree with Shaull that it is a corollary from the facts that the cardinality of programs (Turing machines) is $\aleph_0$ and the set of (meaningful) decision problems is uncountable. I also agree that CH is not necessary (although there is a line of thought which would use it). By viewing a decision problem as an infinite bit string which can be identified by the interval $[0,1)$ which has cardinality of $\mathbb{R}$.
InfinitelyInquisitive
CC BY-SA 3.0
2017-09-07T09:10:35.537Z
@JoshuaGrochow No mention of the result in Turing's and Church's original papers.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-09-13T08:29:49.303Z
@SashoNikolov when you say that every real in $[0,1[$ encodes a meaningful problem, you are implicitly assuming that all real numbers in that interval may be given a "name" $\alpha$, and that it is a meaningful question to ask "what is the $i$-th bit in the (minimal) binary expansion of $\alpha$?".  But this is epistemologically problematic: where do such names come from?  Do you really have $2^{\aleph_0}$ of them? (continues below)
Damiano Mazza
CC BY-SA 3.0
2017-09-13T08:33:08.273Z
The interest (and non-triviality) of undecidability appears when you realize that not only the answers (i.e., the algorithms), but also the *meaningful questions* are countable, because in general we can only name countably many of them (typically via logical formulas). Turing, Church & co. proved the existence of meaningful "questions" (technically expressible by $\Sigma^0_1$ formulas) for which there is no "answer". I think the OP's question is interesting because it puts the finger on this subtle issue (although the OP him/herself does not seem to have realized it).
Damiano Mazza
CC BY-SA 3.0
2017-09-13T20:15:55.890Z
@DamianoMazza your notion of "meaningful" is much more restrictive than mine. I simply meant that it's a well-defined language. I think it's misleading to only call languages explicitly encoded as a logical formula "meaningful". I would prefer to call them definable or something like that.
Sasho Nikolov
CC BY-SA 3.0
2017-09-14T08:51:04.690Z
@SashoNikolov granted, "definable" is a better word for the particular technical sense I invoked, but I still think that the meaningfulness of all subsets of $\{0,1\}^\ast$ as decision problems is questionable. Taking all such subsets as decision problems is a very convenient, workable definition, I'm not questioning that; I'm just saying that one must be aware that it may sometimes be too broad. For instance, it makes the negative result mentioned by the OP (not all problems are decidable) void of content and a search for its "original proof" pointless, unlike undecidability of halting.
Damiano Mazza
CC BY-SA 3.0
2017-09-18T08:27:23.953Z
@DamianoMazza, SashoNikolov: So the question whether this "standard argument" for the validity of the corollary ultimately boils down to the question whether we know if the definable real numbers (in the interval $[0,1)$) are uncountable or not, isn't it? I know that there are definable real numbers which are not computable (Chaitin's "constant", Specker sequences, ...), however I have no idea if they or abundant and uncountable or just rare phenomena. Any ideas and hints about results in this direction?
InfinitelyInquisitive
CC BY-SA 3.0
2017-09-18T09:31:20.277Z
If by definability you mean definable by an arithmetical formula, then there are only countably many definable reals and the question of how many are undecidable (e.g. in terms of their measure as a subset of the Lebesgue-measurable set $[0,1[$) is non-trivial.  I have no idea how to answer it.  E.g. you may restrict to $\Sigma^0_1$ sets. Is there any result giving us an idea of how many of these are decidable? (I.e., how many are also in $\Pi^0_1$?).  Maybe you can ask this question on Mathoverflow?  I am pretty sure that you'll find interesting answers over there.
Damiano Mazza
CC BY-SA 3.0
2017-09-18T09:52:03.520Z
For example, J.D. Hamkins's answer to [this question](https://mathoverflow.net/q/10358/45027) (as well as [this one](https://mathoverflow.net/q/35912/45027)) is somehow related, although does not answer the question.  It would answer the question if, instead of a set of Turing machines, one could find a set of $\Sigma^0_1$ formulas of measure 1 (over the set of all $\Sigma^0_1$ formulas) which are all decidable.  Note that Henkins and Miasnikov's result immediately gives a set of decidable $\Sigma^0_1$ sets, but it is not clear what its measure is.
Damiano Mazza
CC BY-SA 3.0
2017-09-20T09:00:30.090Z
@Damiano: Thanks for the hint/links. Indeed, Hamkins' work seems to deal quite a bit with this problem. I need to dig into that :-)
InfinitelyInquisitive
<computability>
Original proof that "almost all decision problems are uncomputable"?
InfinitelyInquisitive
# Original proof that "almost all decision problems are uncomputable"?

(Asked by: username_0 on 2017-09-05)

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

**Tags:** computability

> **Comments:**
> **username_1**: It's an immediate result by a counting argument (or rather, by showing that the measure of a countable set is 0).  
> **username_0**: Thank you, username_1. I am aware of the usual argument, although I only found very few sources. But none of them seems to be the original source or referring to it. The reason that I've asked is that I try to understand basically two things: (1) if the proof uses the CH (I think it is not necessary, although a "quick argument" via 2^N" might use it), and (2) if we can really associate to every infinite bit string a meaningful problem. (2) would be necessary in my opinion to make the argument valid.  
> **username_0**: The usual argument actually not only says/requires that every decision problem can be encoded by an infinite bit string (which is true, of course), but also that every infinite bit string (hence at least every real number x \in [0,1]) encodes a meaningful problem. Otherwise we cannot be sure whether the set of infinite bit strings which encodes meaningful problems is not in fact just a countable subset of all infinite bit strings. (2) seems to be an issue between the syntax and the semantics of (decision) problems.  
> **username_0**: (I should probably add that with "CH" I mean the continuum hypothesis.)  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_3**: I wouldn't be surprised if it's even mentioned in Turing's or Church's original paper.  
> **username_4**: 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.  
> **username_4**: 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.  
> **username_0**: Thanks Sasho! It was exactly your argument about the converse which I didn't see. Now that it is clear to me that also every $x \in [0,1)$ does encode a meaningful problem, I agree with username_1 that it is a corollary from the facts that the cardinality of programs (Turing machines) is $\aleph_0$ and the set of (meaningful) decision problems is uncountable. I also agree that CH is not necessary (although there is a line of thought which would use it). By viewing a decision problem as an infinite bit string which can be identified by the interval $[0,1)$ which has cardinality of $\mathbb{R}$.  
> **username_5**: @JoshuaGrochow No mention of the result in Turing's and Church's original papers.  
> **username_6**: @SashoNikolov when you say that every real in $[0,1[$ encodes a meaningful problem, you are implicitly assuming that all real numbers in that interval may be given a "name" $\alpha$, and that it is a meaningful question to ask "what is the $i$-th bit in the (minimal) binary expansion of $\alpha$?".  But this is epistemologically problematic: where do such names come from?  Do you really have $2^{\aleph_0}$ of them? (continues below)  
> **username_6**: The interest (and non-triviality) of undecidability appears when you realize that not only the answers (i.e., the algorithms), but also the *meaningful questions* are countable, because in general we can only name countably many of them (typically via logical formulas). Turing, Church & co. proved the existence of meaningful "questions" (technically expressible by $\Sigma^0_1$ formulas) for which there is no "answer". I think the OP's question is interesting because it puts the finger on this subtle issue (although the OP him/herself does not seem to have realized it).  
> **username_4**: @DamianoMazza your notion of "meaningful" is much more restrictive than mine. I simply meant that it's a well-defined language. I think it's misleading to only call languages explicitly encoded as a logical formula "meaningful". I would prefer to call them definable or something like that.  
> **username_6**: @SashoNikolov granted, "definable" is a better word for the particular technical sense I invoked, but I still think that the meaningfulness of all subsets of $\{0,1\}^\ast$ as decision problems is questionable. Taking all such subsets as decision problems is a very convenient, workable definition, I'm not questioning that; I'm just saying that one must be aware that it may sometimes be too broad. For instance, it makes the negative result mentioned by the OP (not all problems are decidable) void of content and a search for its "original proof" pointless, unlike undecidability of halting.  
> **username_0**: @DamianoMazza, SashoNikolov: So the question whether this "standard argument" for the validity of the corollary ultimately boils down to the question whether we know if the definable real numbers (in the interval $[0,1)$) are uncountable or not, isn't it? I know that there are definable real numbers which are not computable (Chaitin's "constant", Specker sequences, ...), however I have no idea if they or abundant and uncountable or just rare phenomena. Any ideas and hints about results in this direction?  
> **username_6**: If by definability you mean definable by an arithmetical formula, then there are only countably many definable reals and the question of how many are undecidable (e.g. in terms of their measure as a subset of the Lebesgue-measurable set $[0,1[$) is non-trivial.  I have no idea how to answer it.  E.g. you may restrict to $\Sigma^0_1$ sets. Is there any result giving us an idea of how many of these are decidable? (I.e., how many are also in $\Pi^0_1$?).  Maybe you can ask this question on Mathoverflow?  I am pretty sure that you'll find interesting answers over there.  
> **username_6**: For example, J.D. Hamkins's answer to [this question](https://mathoverflow.net/q/10358/45027) (as well as [this one](https://mathoverflow.net/q/35912/45027)) is somehow related, although does not answer the question.  It would answer the question if, instead of a set of Turing machines, one could find a set of $\Sigma^0_1$ formulas of measure 1 (over the set of all $\Sigma^0_1$ formulas) which are all decidable.  Note that Henkins and Miasnikov's result immediately gives a set of decidable $\Sigma^0_1$ sets, but it is not clear what its measure is.  
> **username_0**: @Damiano: Thanks for the hint/links. Indeed, Hamkins' work seems to deal quite a bit with this problem. I need to dig into that :-)  

---

## 1 answers

### Answer by username_0 on 2017-09-05. Score: 3 | Accepted answer

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 username_4'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 username_6 (see in the comments above), which I need to check/think about first.


---

