Path: ...!local-3.nntp.ord.giganews.com!Xl.tags.giganews.com!local-4.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 04 Apr 2025 03:15:42 +0000
Subject: Re: Cantor Diagonal Proof
Newsgroups: comp.theory
References: <vsn1fu$1p67k$1@dont-email.me>
 <7EKdnTIUz9UkpXL6nZ2dnZfqn_ednZ2d@brightview.co.uk>
 <vsng73$27sdj$1@dont-email.me>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Fri, 4 Apr 2025 04:15:39 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
MIME-Version: 1.0
In-Reply-To: <vsng73$27sdj$1@dont-email.me>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <gGKdnZiYPJVC03L6nZ2dnZfqn_udnZ2d@brightview.co.uk>
Lines: 27
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-hFuBTfAZbsTD5fjAG83CsQr7bsxtKbFfYdgzCt+95qcnVao2W6zpxkv0XOYz4W8f3nUS0jitJ/4GFhD!gquAq/4rbQXayuZJtBV9fQvd7yhggo1ik5EO/m1O9jhn5N2UrhL/F9YIwZO0eTlUa87rE3OYR1zb!FATotsknxyuI2A+5ylM49+M0DR0=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 2249

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


Mike.