Re: Cantor Diagonal Proof

On 05/04/2025 08:38, Lawrence D'Oliveiro wrote:

On Fri, 4 Apr 2025 09:16:17 +0100, Richard Heathfield wrote:
 

Since all elements (except your two openers) begin with a 3, none of
them start 12, and so after just two iterations we have already
constructed a number that's not in the infinite list.

 Remember that the hypothesis of the Cantor “proof” is that the list is
already supposed to contain every computable number.

On that we can agree. The proof works for any list.

The fact that the
contruction succeeds for your list examples does not mean it will succeed
with mine. Remember, the “proof” depends on it succeeding in the general
case, with every possible list.

Indeed it does. Let's use some syntax.
Let the list be digit_t C[inf][inf] (I'm using a gcc extension that allows infinitely sized arrays). Let the diagonal be D[inf]
Cantor's construction can be expressed as:
for(n = 0; n <= inf; n++)
{
   D[n] = (C[n][n] + 1) % 10;
}
Cantor correctly reasons that, at the point where Achilles catches the tortoise, the number stored in D does not appear in any of C's rows (or columns, come to that).
Your argument appears to be that, since C contains all computable numbers, and since we just computed D, D must already be in C.
But to be computable, numbers must be computed in a finite number of steps. To compute D requires /infinite/ steps. We can reason about D without taking forever over it, but we can't /compute/ it this side of eternity.
You wrote: "But if there is an algorithm for computing the number"
But there isn't. Diamonds are forever, but algorithms must terminate.
--
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