Re: Cantor Diagonal Proof

On 06/04/2025 19:37, Mike Terry wrote:

On 06/04/2025 18:04, Richard Heathfield wrote:

On 06/04/2025 17:24, Mike Terry wrote:

On 06/04/2025 11:52, Richard Heathfield wrote:

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.

>
Cantor made no reference to computability or computable numbers.

>
Nevertheless, that's precisely what Mr D'Oliveiro is talking about. From the start of the thread:
>
"The Cantor diagonal construction is an algorithm for computing an incomputable number. But if there is an algorithm for computing the number, then it is by definition a computable number."
>
<snip>
>

 Sure, but... I'm still not clear on whether OP is expecting/requiring the Cantor list to be a list of computable numbers.  I don't believe he has stated that anywhere...  He just keeps saying the missing number is computable.

He has also said that it must have a match in the list, so I suppose he envisages the list to be of computable numbers.

2. Let D be the Cantor diagonal, eg via
>
for(n = 0; n <= inf; n++)
{
   D[n] = (C[n][n] + 1) % 10;
}

>

[...]

>
It's just shorthand. I'm very willing to consider suggestions for alternative ways to convey meaning so succinctly.

 The "D[n] = (C[n][n] + 1) % 10" bit is no problem, but the for loop is definitely encouraging people to think of the whole thing as some kind of supertask

Point taken, but the n<=inf should clue them in that this isn't one of those supertasks you schedule over a long weekend and pick up your output deck on Tuesday morning.

I'd have just said that the D was the unique real number whose n'th digit is
     D[n] :=   5  [if   C[n][n] != 5]
              6  [otherwise]

Fair enough.

(no need for procedural loops...  also sidesteps the whole 0.999999... discussion we've thankfully not had)

You had to say it out loud, didn't you? ;-)

Hmmm, maybe you're talking about applying Cantor's argument to the list of computable numbers? Cantor never did that.

>
No, but Mr D'Oliveiro did.

 I don't see anywhere that he says the list is a list of computable numbers - just where he says the missing number must be computable.

...and he says it's not missing either, which strongly suggests that the list he thinks it isn't missing from is a list of computable numbers.
<snip>

OP's main problem seems to be that he doesn't understand that a computable real has a /finite/ definition via an algorithm/TM, not a sequence of ever larger TMs that can each compute just finite digit prefixes.  Computing the anti-diag requires the Cantor list as input, which cannot be packaged into a finite amount of data.  Maybe OP has something else in mind but simply hasn't expressed it anywhere so people can't tell what he's actually getting at.  (A bit like assuming the numbers in the list are computable without bothering to actually say that. :) )  Or maybe OP is trolling or a just confused about things, hard to say.

I'm not yet convinced he's trolling, but of course I could be mistaken.
--
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