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: Fri, 4 Apr 2025 04:35:59 +0100
Organization: Fix this later
Lines: 43
Message-ID: <vsnk2v$2fc5a$1@dont-email.me>
References: <vsn1fu$1p67k$1@dont-email.me>
 <7EKdnTIUz9UkpXL6nZ2dnZfqn_ednZ2d@brightview.co.uk>
 <vsng73$27sdj$1@dont-email.me>
 <gGKdnZiYPJVC03L6nZ2dnZfqn_udnZ2d@brightview.co.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 04 Apr 2025 05:36:00 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="36cff22e2bbce90c63e390e25cbe9050";
	logging-data="2601130"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19TKkiWkg2V/9y2dNTpnEe/789MlBUHJ3cMxbIUTJneXw=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:PYix87PRzWzGXic4JWsir/PKNWg=
In-Reply-To: <gGKdnZiYPJVC03L6nZ2dnZfqn_udnZ2d@brightview.co.uk>
Content-Language: en-GB
Bytes: 2694

On 04/04/2025 04:15, Mike Terry wrote:
> On 04/04/2025 03:29, Lawrence D'Oliveiro wrote:
>> On Fri, 4 Apr 2025 02:41:09 +0100, Mike Terry wrote:
>>
>>> On 03/04/2025 23:18, Lawrence D'Oliveiro wrote:
>>>
>>>> The Cantor diagonal construction is an algorithm for 
>>>> computing an
>>>> incomputable number.
>>>
>>> It is not an algorithm for computing something.  Algorithms are
>>> instructions that operate on finite inputs and must terminate 
>>> with an
>>> answer at some point for every input.
>>
>> The definition of a “computable number” is that for any integer 
>> N, there
>> is an algorithm that will compute digit N of the number in a 
>> finite
>> sequence of steps.
>>
>> Does the Cantor diagonal construction fit this definition? Yes 
>> it does.
>>
> 
> No it doesn't, because for a computable number the algorithm 
> cannot have an infinite amount of input data.  Typically we would 
> have a TM running with a tape containing just the number N 
> finitely encoded somehow and blank elsewhere.
> 
> The Cantor diagonal construction takes an infinite list as input...

It doesn't have to. The Cantor argument constructs a number that 
is not in the input list and thus proves that the input list, no 
matter how large, is incomplete. Yes, this works with an infinite 
input list, but it works equally well with finite input lists.

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