Re: Cantor Diagonal Proof

On Sun, 6 Apr 2025 17:24:33 +0100, Mike Terry wrote:

Cantor made no reference to computability or computable numbers.

Didn’t Turing apply his argument to them?

In fact, I don't think Cantor proposed the argument for uncountability
of real numbers in this form ...

What form did he give for his proof, then?

Cantor was not concerned with computability.

Did the concept exist in his time?

His proof assumes we have the list as in (1), and constructs (defines) a
new real number which is manifestly not in the list using the well known
diagonal argument.

The drawback with this construction is it fails to converge. That is, at
any point, we only have some finite number of digits of the number that is
supposedly not in the list, yet it can always match some later entry in
the list.

It is an infinite list, after all.

Hmmm, maybe you're talking about applying Cantor's argument to the list
of computable numbers? ...
 
It might seem that the number produced must be computable because the
anti-diagonal "computes" it, but the anti-diagonal "computation" would
only work given infinitely many digits of data out of the list.

Actually, at any point, it only needs a finite number of digits out of a
finite number of entries in the list. The definition of “computability”
doesn’t mean “I can produce infinitely many digits”, but “I can produce as
many digits as you ask for”.