Re: Cantor Diagonal Proof

On 4/13/25 5:23 PM, Lawrence D'Oliveiro wrote:

On Fri, 11 Apr 2025 21:41:48 -0400, Richard Damon wrote:
 

Yes, but since you need the algorithms to compute ALL the numbers in
your code, you can't put them all in.

 But the Cantor construction relies on constructing precisely such a list.
If you can’t put together such a list, then you can’t perform the Cantor
construction.

Yes, you can CONSTRUCT the operation, but not as a computation.
Confusing those terms just breaks your logic.
For the Computability varient of Cantors proof, we can start by using the axiom of choice, *WE* CAN create an ordered list of the computable numbers, by sorting a chosen machine from the infinite set of machines that computes each of the numbers, and then sorting those by a representation of that algorithm.
So, we CAN construct an infinite list of computations, each element of that list can compute its given number to the specified number of digits.
The problem is that this "construction" is not "computable".
Cantor's original counting argument was to show that the reals could not be mapped 1:1 with the counting numbers, as any such claimed mapping HAD to leave out a number (in fact it could be many depending on the base you are using).
Nothing in that arguement even mentioned "computations" and the implied finite algorithm with finite state in the "processor" (excluding the tape).
The later variation applied to that proof shows that if the list of numbers chosen were individually computable, the diagonal can't be, and thus there can't be a single unified computation to compute the nth digit of the nth number, as that would say there was an uncounable number of computable numbers, created from a countable number of machines.