Hacker News new | ask | show | jobs
by Slow_Dog 1020 days ago
The document's initial example of diagonalization doesn't explain it properly. It shows how you can find a binary string that's not in the list; fine. But it's conveniently a list of 5 strings of length 5. It doesn't show how you'd find a new string of length 5 that's not in a list of 6 such strings, or 31 such strings.

I suspect the "conveniently" may drop out of some conversion of a real problem to an abstraction, but that's not explained.
2 comments
thaumasiotes 1020 days ago
> The document's initial example of diagonalization doesn't explain it properly.

> It shows how you can find a binary string that's not in the list; fine. But it's conveniently a list of 5 strings of length 5. It doesn't show how you'd find a new string of length 5 that's not in a list of 6 such strings

This is actually a mistake on your part. It's true that it's possible to find a string of length 5 that isn't already contained in a list of 6 such strings.

But it isn't possible to do that by using diagonalization. The concept of diagonalization is that you differ from the first string in the list at index 1, from the second string in the list at index 2, from the third at index 3, and so on. A list of six strings, to illustrate diagonalization, would require all of the strings to be six digits long.

link
wzdd 1020 days ago
> would require all of the strings to be six digits long

The OP's point (presumably, because it bugged me too) is that the article doesn't make this clear.

link
thaumasiotes 1020 days ago
No, that can't be the point, because Slow_Dog specifically states that the article should show how to find a binary string of length 5 that isn't contained in a list of six such strings:

> It shows how you can find a binary string that's not in the list; fine. But it's conveniently a list of 5 strings of length 5. It doesn't show how you'd find a new string of length 5 that's not in a list of 6 such strings, or 31 such strings.

The reason it's not showing that is that it's showing an example of diagonalization. Slow_Dog would apparently prefer that the article about diagonalization discuss some other technique than diagonalization.

link
quietbritishjim 1020 days ago
I think the missing piece is just note that, for actual proof applications, the length of the individual "strings" and the total number of them is both (countable) infinity, so the size does match.
link
thaumasiotes 1020 days ago
It's not necessary that they match. All you need is that the length of each string is not less than its position in the list.
link