Sujet : Re: Cantor Diagonal Proof
De : rjh (at) *nospam* cpax.org.uk (Richard Heathfield)
Groupes : comp.theoryDate : 07. Apr 2025, 10:11:00
Autres entêtes
Organisation : Fix this later
Message-ID : <vt04r4$38f06$1@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
User-Agent : Mozilla Thunderbird
On 07/04/2025 09:34, Mikko wrote:
On 2025-04-06 10:52:50 +0000, Richard Heathfield said:
On 06/04/2025 11:29, Mikko wrote:
On 2025-04-05 07:38:19 +0000, Lawrence D'Oliveiro said:
>
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. The fact that the
contruction succeeds for your list examples does not mean it will succeed
with mine.
>
How can Cantor's construction fail to succeed on a list?
>
As I understand it, his argument can be summarised as follows:
>
1. Let C[inf][inf] be a list of all the digits of all the computable numbers.
>
2. Let D be the Cantor diagonal, eg via
>
for(n = 0; n <= inf; n++)
{
D[n] = (C[n][n] + 1) % 10;
}
>
3, Because we have computed D, it is a computable number, and therefore it must have an entry in C[, so the construction of D must somehow be in error.
>
>
The flaw, of course, is in overlooking that we required infinitely many steps to derive D. for(n = 0; n <= inf; n++){whatever} is not an algorithm, because by definition algorithms must have at most finitely many steps.
The number D is not computable if the list C is not.
Granted, but I would maintain that D would remain incomputable even if you could wave a magic wand and compute C[].
The counter-assumption was that there is a list of all
computable numbers but not that there is a computable list of
all computable numbers. As the number D is not computable its absence in C is not a contradiction.
Agreed. But I don't think we'll move Mr D'Oliveiro away from his claim quite that easily, as he has evidently mistaken his slippery ground for bedrock.
-- Richard HeathfieldEmail: rjh at cpax dot org dot uk"Usenet is a strange place" - dmr 29 July 1999Sig line 4 vacant - apply within
Cantor Diagonal Proof
Re: Cantor Diagonal Proof