Sujet : Re: Cantor Diagonal Proof
De : news.dead.person.stones (at) *nospam* darjeeling.plus.com (Mike Terry)
Groupes : comp.theoryDate : 04. Apr 2025, 04:15:39
Autres entêtes
Message-ID : <gGKdnZiYPJVC03L6nZ2dnZfqn_udnZ2d@brightview.co.uk>
References : 1 2 3
User-Agent : Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Firefox/91.0 SeaMonkey/2.53.18.2
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.
…