Re: Cantor Diagonal Proof

On 04/04/2025 12:47, Julio Di Egidio wrote:

On 04/04/2025 00:18, Lawrence D'Oliveiro wrote:

The Cantor diagonal construction is an algorithm for computing an
incomputable number.

[As others, inc Julio, have pointed out, it is, as it stands,
neither an algorithm nor a way of computing non-computable numbers.]

To be more precise, it is an argument, not an algorithm, although it
is a fact that "diagonalisation" as a method has become ubiquitous.
BTW, the argument has indeed been proved constructively: or so they
say, I find that debatable as it needs *extensionality*.

But if there is an algorithm for computing the number, then it is by
definition a computable number.

The anti-diagonal is *as computable as the list is*: and the argument
in fact proves there can be no such list, computable or otherwise...
(no complete list of all such *sequences*: the connection to the real
*numbers* is a further step and problem).

Three small additions to Julio's article:
  -- There is an easy construction [left as an exercise] by which to
     construct any given computable number by Cantor's technique.  Of
     course, this has no practical value as you need a program for that
     number in the first place.
  -- The construction of a computable number that differs from every
     number in the list shows that there is no way to construct a list
     of all computable numbers, even though that list corresponds to a
     subset of the [computable] list of all TMs.  Consequences left as
     an exercise.
  -- There are parallels with the [interminable] debates here about the
     HP.  Given a [claimed] "halt decider", P, then there is an easily-
     produced program, P^ [often called here the Linz P^], that P either
     gets wrong or fails to decide.  Thus the claim is incorrect.  Given
     a [claimed] complete list of computables or reals, the Cantor process
     constructs a computable/real number not on the list,  Thus the claim
     is incorrect.  If you don't make the claim, then "so what?", the new
     program/number is only mildly interesting.  That doesn't stop trolls,
     cranks and the confused from jumping up and down about some facet of
     the result, of course.  The rest of us just move on.
--
Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Morel