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: Tue, 8 Apr 2025 01:12:44 +0100
Organization: Fix this later
Lines: 103
Message-ID: <vt1plt$vg8u$1@dont-email.me>
References: <vsn1fu$1p67k$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> <875xjfd5rs.fsf@nosuchdomain.example.com>
 <vt1jpa$n43m$4@dont-email.me> <87tt6zblzl.fsf@nosuchdomain.example.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 08 Apr 2025 02:12:47 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="10800003f1347f6823fd33fbb5a71e8e";
	logging-data="1032478"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+nGbsZpV0qAvY/uI2PyjasTj+mV7luqB7RH2MqGdHciQ=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:nLY70sGgKOQmRnOKQiXeIkSDb/w=
Content-Language: en-GB
In-Reply-To: <87tt6zblzl.fsf@nosuchdomain.example.com>
Bytes: 6005

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