7 ms·

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

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.

quietbritishjim 3y 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.
- thaumasiotes 3y 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.
thaumasiotes 3y 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.
- wzdd 3y 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.
  - thaumasiotes 3y 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.

quietbritishjim 3y 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.

thaumasiotes 3y 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.

thaumasiotes 3y 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.

wzdd 3y 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.
- thaumasiotes 3y 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.