Re: Cantor Diagonal Proof

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