Re: Cantor Diagonal Proof

On 08/04/2025 00:17, 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*

You are not the first to say so.
"I would say you are quoting Turing out of context." - Lawrence D'Oliveira
I repeat:
There is no context before his words because they are the paper's opening words. Here's the context that immediately follows.
"The “computable” numbers may be described briefly as the real
numbers whose expressions as a decimal are calculable by finite
means. Although the subject of this paper is ostensibly the
computable numbers, it is almost equally easy to define and
investigate computable functions of an integral variable or a
real or computable variable, computable predicates, and so forth.
The fundamental problems involved are, however, the same in each
case, and I have chosen the computable numbers for explicit
treatment as involving the least cumbrous technique. I hope
shortly to give an account of the relations of the computable
numbers, functions, and so forth to one another. This will
include a development of the theory of functions of a real
variable expressed in terms of computable numbers. According to
my definition, a number is computable if its decimal can be
written down by a machine." - Alan Turing

it could be taken to imply that pi is not computable (at least that's
the implication I took from it).

"According to my definition, a number is computable if its decimal can be written down by a machine."
Simon Plouffe's spigot algorithm can spit out any hexadecimal digit of pi without even having to calculate its predecessors. If your TM /does/ calculate its predecessors (a finite process) and then converts to base ten (another finite process), it has written it down the decimal for as many places as you have spare tape to write and time to wait. If you are cunning, you will omit the base conversion because Turing's TMs were modest creatures, and he wrote: "The real number whose expression as a binary decimal[...]" which suggests that he is using the term "decimal" a little loosely.

I don't know the full context, but I
presume he clarified that an infinite number of steps might be required
in some cases.

You may presume that, but I can find no evidence to support the claim. I did, however, find this: "When sufficiently many
figures of d have been calculated..." which strongly suggests that Turing doesn't make you wait until the heat death of the universe to claim that a number is computable.

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.

Yes.
I am equally certain that we are also in agreement that Cantor's diagonal construction differs in at least one digit from every number in the list used to construct it.
--
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