18
$\begingroup$

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?)

|cite|improve this question
$\endgroup$
  • 19
    $\begingroup$ Probably it was, but it's not very interesting: most of these problems are basically "random" and not the sort of thing we would care about solving anyway. What the unsolvability of the halting problem shows that there is a particular very interesting and fundamental problem, which would be great if we could solve, that we can't solve. $\endgroup$ – Qiaochu Yuan Nov 22 '17 at 19:06
  • 3
    $\begingroup$ (Turing in particular was motivated by the Entscheidungsproblem, the problem of determining whether a given statement in a first-order theory is provable or not.) $\endgroup$ – Qiaochu Yuan Nov 22 '17 at 19:33
  • $\begingroup$ I'm not sure I understand you. Your argument in the last two paragraphs sounds the same as Turing's original proof to me. Why is trying to solve the halting problem equivalent to trying to find a bijection $\mathbb{N} \rightarrow 2^{\mathbb{N}}$? You could use cardinality to prove that there exists sets $U$ so that no $M$ will halt exactly on inputs in $U$, but this is a much weaker statement. $\endgroup$ – Jair Taylor Nov 23 '17 at 21:05
25
$\begingroup$

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".

|cite|improve this answer
$\endgroup$
  • 14
    $\begingroup$ @PålGD: Your argument implicitly assumes that (a) computable things can be represented by machines, and (b) machines can be numbered. Without a reason to believe those two preliminaries it is not convincing at all, and such a reason has to be based on understanding. $\endgroup$ – hmakholm left over Monica Nov 22 '17 at 19:39
  • 7
    $\begingroup$ Note that the idea of using numbers to (in a mathematically precise way) encode things that are not intrinsically numbers only really arose with Gödel in 1931. And I doubt that "diagonalization" was even recognized as a general class of arguments (rather than a particular proof of Cantor's) until it was applied to computability and proof theory in the 1930s. $\endgroup$ – hmakholm left over Monica Nov 22 '17 at 19:41
  • 6
    $\begingroup$ @PålGD: As long as those finite strings are descriptions in a natural language and you're relying on a human to figure out what they mean, what you have is not really a mathematical argument. It's open to all kinds of doubt about whether your diagonal set is even well-defined because there can be disagreement about what a particular description means (or whether is is clear enough to count). $\endgroup$ – hmakholm left over Monica Nov 22 '17 at 19:48
  • 12
    $\begingroup$ @PålGD "I tried to assume only that every algorithm had a finite description" Sorry, it's 1930. What's an algorithm? $\endgroup$ – David Richerby Nov 22 '17 at 22:41
  • 9
    $\begingroup$ @PålGD "I'm just applying a bijection between the naturals and the set of all finite strings." aka encoding $\endgroup$ – G. Bach Nov 23 '17 at 11:48
19
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I think the assumption is possibly even stronger. Not only must every algorithm have a finite description, they must all have a finite description using the same representation. After all, for any algorithm I can posit a machine which has that particular algorithm as a convenient primitive. But the notion of the Universal Turing Machine is that it doesn't have such convenient primitives. $\endgroup$ – MSalters Nov 23 '17 at 16:33
17
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Is your argument that they actually knew, or is it that they weren't interested? It seems that if they were aware that there was a problem that did not have a corresponding algorithm, then Hilbert would be more careful in his formulation of the 10th problem. $\endgroup$ – Pål GD Nov 22 '17 at 19:40
  • 7
    $\begingroup$ No, you are misunderstanding, Hilbert and co. knew about non-r.e.sets, there are as you say lots of them. But a non-recursive r.e.set is a more subtle problem. As for Hilberts 10th, there are only countably many diophantine equations. $\endgroup$ – Rene Schipperus Nov 22 '17 at 19:49

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.