Re: Cantor Diagonal Proof

Liste des GroupesRevenir à c theory 
Sujet : Re: Cantor Diagonal Proof
De : rjh (at) *nospam* cpax.org.uk (Richard Heathfield)
Groupes : comp.theory
Date : 06. Apr 2025, 20:05:54
Autres entêtes
Organisation : Fix this later
Message-ID : <vsujai$1jtk8$2@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
User-Agent : Mozilla Thunderbird
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

Date Sujet#  Auteur
3 Apr 25 * Cantor Diagonal Proof219Lawrence D'Oliveiro
3 Apr 25 +* Re: Cantor Diagonal Proof2Richard Damon
4 Apr 25 i`- Re: Cantor Diagonal Proof1Lawrence D'Oliveiro
4 Apr 25 +* Re: Cantor Diagonal Proof6Richard Heathfield
4 Apr 25 i`* Re: Cantor Diagonal Proof5Lawrence D'Oliveiro
4 Apr 25 i `* Re: Cantor Diagonal Proof4Richard Heathfield
4 Apr 25 i  `* Re: Cantor Diagonal Proof3Lawrence D'Oliveiro
4 Apr 25 i   `* Re: Cantor Diagonal Proof2Richard Heathfield
4 Apr 25 i    `- Re: Cantor Diagonal Proof1Lawrence D'Oliveiro
4 Apr 25 +* Re: Cantor Diagonal Proof144Mike Terry
4 Apr 25 i+* Re: Cantor Diagonal Proof141Lawrence D'Oliveiro
4 Apr 25 ii`* Re: Cantor Diagonal Proof140Mike Terry
4 Apr 25 ii +* Re: Cantor Diagonal Proof131Richard Heathfield
4 Apr 25 ii i`* Re: Cantor Diagonal Proof130Lawrence D'Oliveiro
4 Apr 25 ii i `* Re: Cantor Diagonal Proof129Richard Heathfield
4 Apr 25 ii i  `* Re: Cantor Diagonal Proof128Lawrence D'Oliveiro
4 Apr 25 ii i   `* Re: Cantor Diagonal Proof127Richard Heathfield
4 Apr 25 ii i    `* Re: Cantor Diagonal Proof126Lawrence D'Oliveiro
4 Apr 25 ii i     `* Re: Cantor Diagonal Proof125Richard Heathfield
4 Apr 25 ii i      `* Re: Cantor Diagonal Proof124Lawrence D'Oliveiro
4 Apr 25 ii i       `* Re: Cantor Diagonal Proof123Richard Heathfield
4 Apr 25 ii i        `* Re: Cantor Diagonal Proof122Lawrence D'Oliveiro
4 Apr 25 ii i         `* Re: Cantor Diagonal Proof121Richard Heathfield
5 Apr 25 ii i          `* Re: Cantor Diagonal Proof120Lawrence D'Oliveiro
5 Apr 25 ii i           +* Re: Cantor Diagonal Proof25Richard Heathfield
6 Apr 25 ii i           i`* Re: Cantor Diagonal Proof24Lawrence D'Oliveiro
6 Apr 25 ii i           i `* Re: Cantor Diagonal Proof23Richard Heathfield
6 Apr 25 ii i           i  `* Re: Cantor Diagonal Proof22Lawrence D'Oliveiro
6 Apr 25 ii i           i   +* Re: Cantor Diagonal Proof3Richard Heathfield
6 Apr 25 ii i           i   i`* Re: Cantor Diagonal Proof2Lawrence D'Oliveiro
6 Apr 25 ii i           i   i `- Re: Cantor Diagonal Proof1Richard Heathfield
6 Apr 25 ii i           i   `* Re: Cantor Diagonal Proof18wij
6 Apr 25 ii i           i    +* Re: Cantor Diagonal Proof5Richard Heathfield
6 Apr 25 ii i           i    i`* Re: Cantor Diagonal Proof4wij
6 Apr 25 ii i           i    i `* Re: Cantor Diagonal Proof3Richard Heathfield
6 Apr 25 ii i           i    i  `* Re: Cantor Diagonal Proof2wij
6 Apr 25 ii i           i    i   `- Re: Cantor Diagonal Proof1Richard Heathfield
6 Apr 25 ii i           i    `* Re: Cantor Diagonal Proof12Mikko
6 Apr 25 ii i           i     `* Re: Cantor Diagonal Proof11wij
7 Apr 25 ii i           i      `* Re: Cantor Diagonal Proof10Mikko
7 Apr 25 ii i           i       `* Re: Cantor Diagonal Proof9wij
7 Apr 25 ii i           i        +* Re: Cantor Diagonal Proof3Richard Heathfield
7 Apr 25 ii i           i        i`* Re: Cantor Diagonal Proof2wij
7 Apr 25 ii i           i        i `- Re: Cantor Diagonal Proof1Richard Heathfield
8 Apr 25 ii i           i        `* Re: Cantor Diagonal Proof5Mikko
8 Apr 25 ii i           i         +* Re: Cantor Diagonal Proof3Richard Heathfield
8 Apr 25 ii i           i         i`* Re: Cantor Diagonal Proof2wij
8 Apr 25 ii i           i         i `- Re: Cantor Diagonal Proof1Richard Heathfield
8 Apr 25 ii i           i         `- Re: Cantor Diagonal Proof1wij
5 Apr 25 ii i           +* Re: Cantor Diagonal Proof61Andy Walker
6 Apr 25 ii i           i`* Re: Cantor Diagonal Proof60Lawrence D'Oliveiro
6 Apr 25 ii i           i +* Re: Cantor Diagonal Proof39Richard Heathfield
6 Apr 25 ii i           i i`* Re: Cantor Diagonal Proof38Lawrence D'Oliveiro
6 Apr 25 ii i           i i `* Re: Cantor Diagonal Proof37Richard Heathfield
7 Apr 25 ii i           i i  `* Re: Cantor Diagonal Proof36Lawrence D'Oliveiro
7 Apr 25 ii i           i i   `* Re: Cantor Diagonal Proof35Richard Heathfield
7 Apr 25 ii i           i i    +* Re: Cantor Diagonal Proof32Keith Thompson
7 Apr 25 ii i           i i    i`* Re: Cantor Diagonal Proof31Richard Heathfield
8 Apr 25 ii i           i i    i `* Re: Cantor Diagonal Proof30Keith Thompson
8 Apr 25 ii i           i i    i  +- Re: Cantor Diagonal Proof1Richard Heathfield
8 Apr 25 ii i           i i    i  `* Re: Cantor Diagonal Proof28Richard Damon
10 Apr 25 ii i           i i    i   `* Re: Cantor Diagonal Proof27Lawrence D'Oliveiro
10 Apr 25 ii i           i i    i    +- Re: Cantor Diagonal Proof1Richard Heathfield
10 Apr 25 ii i           i i    i    +* Re: Cantor Diagonal Proof19Richard Damon
11 Apr 25 ii i           i i    i    i`* Re: Cantor Diagonal Proof18Lawrence D'Oliveiro
11 Apr 25 ii i           i i    i    i `* Re: Cantor Diagonal Proof17Richard Damon
11 Apr 25 ii i           i i    i    i  `* Re: Cantor Diagonal Proof16Lawrence D'Oliveiro
11 Apr 25 ii i           i i    i    i   `* Re: Cantor Diagonal Proof15Richard Damon
11 Apr 25 ii i           i i    i    i    `* Re: Cantor Diagonal Proof14Lawrence D'Oliveiro
12 Apr 25 ii i           i i    i    i     `* Re: Cantor Diagonal Proof13Richard Damon
13 Apr 25 ii i           i i    i    i      `* Re: Cantor Diagonal Proof12Lawrence D'Oliveiro
13 Apr 25 ii i           i i    i    i       +* Re: Cantor Diagonal Proof10Keith Thompson
13 Apr 25 ii i           i i    i    i       i+- Re: Cantor Diagonal Proof1Jeff Barnett
14 Apr 25 ii i           i i    i    i       i+- Re: Cantor Diagonal Proof1Richard Damon
14 Apr 25 ii i           i i    i    i       i`* Re: Cantor Diagonal Proof7Lawrence D'Oliveiro
14 Apr 25 ii i           i i    i    i       i +- Re: Cantor Diagonal Proof1Richard Damon
14 Apr 25 ii i           i i    i    i       i +* Re: Cantor Diagonal Proof4Keith Thompson
14 Apr 25 ii i           i i    i    i       i i`* Re: Cantor Diagonal Proof3Lawrence D'Oliveiro
15 Apr 25 ii i           i i    i    i       i i +- Re: Cantor Diagonal Proof1Keith Thompson
15 Apr 25 ii i           i i    i    i       i i `- Re: Cantor Diagonal Proof1Mikko
14 Apr 25 ii i           i i    i    i       i `- Re: Cantor Diagonal Proof1Richard Heathfield
14 Apr 25 ii i           i i    i    i       `- Re: Cantor Diagonal Proof1Richard Damon
10 Apr 25 ii i           i i    i    `* Re: Cantor Diagonal Proof6Mikko
11 Apr 25 ii i           i i    i     `* Re: Cantor Diagonal Proof5Lawrence D'Oliveiro
11 Apr 25 ii i           i i    i      +- Re: Cantor Diagonal Proof1Richard Damon
11 Apr 25 ii i           i i    i      +- Re: Cantor Diagonal Proof1Richard Heathfield
11 Apr 25 ii i           i i    i      +- Re: Cantor Diagonal Proof1Mikko
14 Apr 25 ii i           i i    i      `- Re: Cantor Diagonal Proof1Mikko
10 Apr 25 ii i           i i    `* Re: Cantor Diagonal Proof2Lawrence D'Oliveiro
10 Apr 25 ii i           i i     `- Re: Cantor Diagonal Proof1Richard Heathfield
6 Apr 25 ii i           i `* Re: Cantor Diagonal Proof20Andy Walker
6 Apr 25 ii i           i  `* Re: Cantor Diagonal Proof19Lawrence D'Oliveiro
6 Apr 25 ii i           i   +- Re: Cantor Diagonal Proof1Richard Heathfield
6 Apr 25 ii i           i   `* Re: Cantor Diagonal Proof17Jeff Barnett
7 Apr 25 ii i           i    `* Re: Cantor Diagonal Proof16Lawrence D'Oliveiro
7 Apr 25 ii i           i     `* Re: Cantor Diagonal Proof15Jeff Barnett
7 Apr 25 ii i           i      `* Re: Cantor Diagonal Proof14Lawrence D'Oliveiro
7 Apr 25 ii i           i       +* Re: Cantor Diagonal Proof12Richard Damon
8 Apr 25 ii i           i       i`* Re: Cantor Diagonal Proof11Lawrence D'Oliveiro
8 Apr 25 ii i           i       i `* Re: Cantor Diagonal Proof10Richard Damon
10 Apr 25 ii i           i       i  `* Re: Cantor Diagonal Proof9Lawrence D'Oliveiro
7 Apr 25 ii i           i       `- Re: Cantor Diagonal Proof1Richard Heathfield
6 Apr 25 ii i           `* Re: Cantor Diagonal Proof33Mikko
4 Apr 25 ii `* Re: Cantor Diagonal Proof8Lawrence D'Oliveiro
4 Apr 25 i`* Re: Cantor Diagonal Proof2wij
4 Apr 25 +* Re: Cantor Diagonal Proof25Mikko
4 Apr 25 +* Re: Cantor Diagonal Proof20Julio Di Egidio
5 Apr 25 +* Re: Cantor Diagonal Proof --- PLO6olcott
13 Apr 25 +* Re: Cantor Diagonal Proof14Lawrence D'Oliveiro
15 Apr 25 `- Re: Cantor Diagonal Proof1Lawrence D'Oliveiro

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal