Re: Cantor Diagonal Proof

Richard Heathfield <rjh@cpax.org.uk> writes:

On 07/04/2025 22:24, Keith Thompson wrote:

Richard Heathfield <rjh@cpax.org.uk> writes:

On 07/04/2025 08:33, Lawrence D'Oliveiro wrote:

[...]

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

[...]
That's a little too briefly.

>
I'll be sure to take it up with Turing next time I see him. What was
he thinking?
>

Quoting Wikipedia:
     In mathematics, computable numbers are the real numbers that can
     be computed to within any desired precision by a finite,
     terminating algorithm.
By dropping the "to within any desired precision"

>
It wasn't there to drop.
>

your description implies (unintentionally, I'm sure) that pi is not
computable.

>
Not my description; Alan Turing's description. Those quotation marks
around the words weren't there just for fun.

Yes, that's what Turing wrote.  I suggest that *if taken out of context*
it could be taken to imply that pi is not computable (at least that's
the implication I took from it).  I don't know the full context, but I
presume he clarified that an infinite number of steps might be required
in some cases.

Turing's paper is here:

https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf

I'm certain we're both in agreement that (a) all the digits of pi cannot
be computed by any algorithm or Turing machine in a finite number of
steps, but (b) any digit of pi can be computed in a finite number of
steps by some algorith or Turing machine.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */