Re: Cantor Diagonal Proof

On 4/7/25 7:17 PM, Keith Thompson wrote:

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.
 

Note, the paper is describing that the ALGORITHM is finite, not that the number of steps it makes if finite, and the machine that is processing it has only finite states (not counting the infinite tape attached to it where the results are placed).
The paper clearly talks about the process continuing indefinitely.