Re: Cantor Diagonal Proof

On 06/04/2025 21:25, Lawrence D'Oliveiro wrote:
<snip>

The drawback with this construction is it fails to converge. That is, at
any point, we only have some finite number of digits of the number that is
supposedly not in the list, yet it can always match some later entry in
the list.
 It is an infinite list, after all.

By the time you get to the bottom of the infinite list, you'll find that you never found a match after all. Compare the nth number, and you'll find that it differs in the nth digit.

Hmmm, maybe you're talking about applying Cantor's argument to the list
of computable numbers? ...
>
It might seem that the number produced must be computable because the
anti-diagonal "computes" it, but the anti-diagonal "computation" would
only work given infinitely many digits of data out of the list.

 Actually, at any point, it only needs a finite number of digits out of a
finite number of entries in the list.

But that's not the number we're building with the diagonal construction. We want the /whole/ diagonal, not an infinitesimally microscopic subset.

The definition of “computability”
doesn’t mean “I can produce infinitely many digits”, but “I can produce as
many digits as you ask for”.

We want them all, please, and that is why the number is incomputable.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within