Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Thu, 10 Apr 2025 02:39:19 +0100
Organization: Fix this later
Lines: 81
Message-ID: <vt77g9$1sprc$1@dont-email.me>
References: <vsn1fu$1p67k$1@dont-email.me>
 <7EKdnTIUz9UkpXL6nZ2dnZfqn_ednZ2d@brightview.co.uk>
 <vsng73$27sdj$1@dont-email.me>
 <gGKdnZiYPJVC03L6nZ2dnZfqn_udnZ2d@brightview.co.uk>
 <vsnk2v$2fc5a$1@dont-email.me> <vsnmtg$2i4qp$3@dont-email.me>
 <vsno7m$2g4cd$3@dont-email.me> <vsnp0o$2ka6o$2@dont-email.me>
 <vsnpv4$2g4cd$6@dont-email.me> <vsntes$2osdn$1@dont-email.me>
 <vsntv3$2paf9$1@dont-email.me> <vso1a0$2sf7o$1@dont-email.me>
 <vso2ff$2tj1d$2@dont-email.me> <vso3rj$2vems$2@dont-email.me>
 <vso4gh$2vg3b$1@dont-email.me> <vsqmlb$1ktm5$6@dont-email.me>
 <vsr1ae$1pr17$2@dont-email.me> <vst4nm$8daf$2@dont-email.me>
 <vst8ci$aeqh$3@dont-email.me> <vsutjt$21mp2$2@dont-email.me>
 <vsuvp1$227l5$1@dont-email.me> <vsvv3h$36pju$2@dont-email.me>
 <vt01u5$38f07$1@dont-email.me> <vt74ed$1pl6i$4@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 10 Apr 2025 03:39:21 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="3fff1669ce0240e544cc21f2a470e8cc";
	logging-data="1992556"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/SkGL4zS9SVIdnIDo1/CFH+e/EK1R28OlBCvfiDew0wA=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:7TYnS5Vm7+dB05bfAPMFIhxsAp8=
In-Reply-To: <vt74ed$1pl6i$4@dont-email.me>
Content-Language: en-GB
Bytes: 5197

On 10/04/2025 01:47, Lawrence D'Oliveiro wrote:
> On Mon, 7 Apr 2025 09:21:25 +0100, Richard Heathfield wrote:
> 
>> On 07/04/2025 08:33, Lawrence D'Oliveiro wrote:
>>
>>> On Sun, 6 Apr 2025 23:38:25 +0100, Richard Heathfield wrote:
>>>
>>>> On 06/04/2025 23:01, Lawrence D'Oliveiro wrote:
>>>>
>>>>> On Sun, 6 Apr 2025 07:53:06 +0100, Richard Heathfield wrote:
>>>>>
>>>>>> After infinitely many steps ...
>>>>>
>>>>> I.e. never.
>>>>
>>>> If you mean you can never know all the digits, hey, you're right.
>>>> No algorithm can derive the number. It's incomputable.
>>>
>>> That’s not what “incomputable” means.
>>
>> Yeah, it is. We've already had this argument. Turing won:  "The
>> "computable" numbers may be described briefly as the real numbers whose
>> expressions as a decimal are calculable by finite means."
> 
> You didn’t even read to the end of his first paragraph: “According to my
> definition, a number is computable if its decimal can be written down by a
> machine”.
> 
> Second paragraph: “The include, for instance, the real parts of all
> algebraic numbers, the real parts of the zeros of the Bessel functions,
> the numbers π, e, etc”.
> 
> Tell me your interpretation of how the digits of π “as a decimal are
> calculable by finite means”.

I don't have to. Turing uses it as an example:

We shall say that a sequence fin of computable numbers converges
computably if there is a computable integral valued function N(e) 
of the computable variable e, such that we can show that, if e > 
0 and n > N(e) and m > N(e), then |\beta_n - \beta_m| < e.
We can then show that [...] (viii) The limit of a computably 
convergent sequence is computable. From (viii) and \pi = 
4(1—1/3+1/5-...) we deduce that \pi is computable.

Nowadays, he wouldn't have to do that because he could use the 
Bailey–Borwein–Plouffe formula to spit out as many hexits as he 
wants, one by one.

>> Like anything in mathematics, if you're going to overturn a
>> long-established proof you're going to need a better argument than that
>> you don't understand what it proves.
> 
> Go on, then, show the flaw in my proof by induction. Because if proof-by-
> induction is not a “long-established proof”, then tell me what is.

Proof by induction is not a long-established proof. It's a 
long-established /technique/. Some proofs by induction are 
correct, but flaws in inductive proofs are hardly rare. Here are 
a few: <https://brilliant.org/wiki/flawed-induction-proofs/> 
<https://math.colorado.edu/~kstange/teaching-resources/discrete/HildebrandFalseInductionProofs.pdf> 
<https://home.cs.colorado.edu/~yuvo9296/courses/csci2824/sect12-induction2.html>

The flaw in your argument is in the claim that "there is an 
algorithm for computing the number" (your words, in the OP).

Cantor's diagonal construction is not an algorithm; it's an 
observation that allows us to deduce that "If s1, s2, ... , sn, 
.... is any enumeration of elements from T,[note 3] then an 
element s of T can be constructed that doesn't correspond to any 
sn in the enumeration."

The "construction" is not an algorithm that one might execute, 
but it does not need to be executed to be understood.

-- 
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