Why did nobody prove undecidability by the "too many problems" argument?

To the best of my knowledge, the two major breakthroughs in regarding negative results in computation/recursion theory came in 1936 by Church and Turing. They both prove that some variant of the Halting problem was undecidable.

However, a very simple proof of the statement "There is an undecidable problem" already existed at that time, namely the fact that there are simply too many problems and too few algorithms.

Assuming that any algorithm has a finite description, and that they take natural numbers as input, we are trying to make a bijection between the natural numbers $\mathbb{N}$ and its powerset $2^{\mathbb{N}}$.

Adopting Cantor's diagonal argument to Machines, we can observe that if $\mathcal{M} = \{M_i \mid i \in \mathbb{N}\}$ is the set of machines, and for every machine $M \in \mathcal{M}$, that $M(n)$ is either yes (halts) or no (does not halt), for $n \in \mathbb{N}$.

Then we can construct the set $$U = \{i \in \mathbb{N} \mid M_i(i) \text{ is no} \}$$ like Cantor would, and pick the $i$ s.t. the domain of $M_i$ is $U$, and ask whether $i \in U$, in both cases reaching a contradiction.

Question: Why wasn't this discovered between 1875/90 and 1935? (Or was it?)

Solution 1:

Why wasn't this discovered between 1875/90 and 1935? (Or was it?)

The argument you sketch could not be discovered until one had a sufficiently formalized understanding of what "a recipe for computation" even means to be able to argue that there are countably many of them.

Such an understanding had been brewing slowly in the first decades of the 1900s, fueled mostly by foundational considerations -- but it doesn't really seem to have been until the 1920s that people began to seriously consider that perhaps they shouldn't be thinking in terms of "what is the way to do such-and-such?" but in terms of "is there any possible way to do such-and-such?" And before the latter question gets asked there is no real interest in getting all pedantic about what counts or doesn't count as "a way".

Solution 2:

This is similar to Rene Schipperus's answer, but instead of working with recursive enumerability, I'll use your notion of "finite description". You say that every algorithm must have a finite description, and I agree. But I'd also say that a problem must have a finite description. A random, indescribable set of natural numbers should not be considered a problem, because it can't be "asked".

The essential point of undecidability theorems is not the triviality that some subsets of $\mathbb N$ have no decision procedure, but that some definable subsets of $\mathbb N$ have no decision procedure. (Rene's answer concerns the stronger result that the subsets in question can be taken to be not only definable but recursively enumerable.)

Solution 3:

There are not too many problems. So yes there are continuum many subsets of $\mathbb{N}$, but there are only $\aleph_0$ many recursively enumerable subsets. The undecidibility theorem, if you wish to so call it, is that there are non-recursive, recursively enumerable sets. For example a Turing machine a finiteset of instructions. There are only $\aleph_0$ many of them.