Path: ...!eternal-september.org!feeder3.eternal-september.org!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Cantor Diagonal Proof
Date: Tue, 8 Apr 2025 21:16:20 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <54f7328d108ed415d2b880c558fe0b3ba5656800@i2pn2.org>
References: <vsn1fu$1p67k$1@dont-email.me>
 <7EKdnTIUz9UkpXL6nZ2dnZfqn_ednZ2d@brightview.co.uk>
 <vsng73$27sdj$1@dont-email.me>
 <gGKdnZiYPJVC03L6nZ2dnZfqn_udnZ2d@brightview.co.uk>
 <vsnk2v$2fc5a$1@dont-email.me> <vsnmtg$2i4qp$3@dont-email.me>
 <vsno7m$2g4cd$3@dont-email.me> <vsnp0o$2ka6o$2@dont-email.me>
 <vsnpv4$2g4cd$6@dont-email.me> <vsntes$2osdn$1@dont-email.me>
 <vsntv3$2paf9$1@dont-email.me> <vso1a0$2sf7o$1@dont-email.me>
 <vso2ff$2tj1d$2@dont-email.me> <vso3rj$2vems$2@dont-email.me>
 <vso4gh$2vg3b$1@dont-email.me> <vsqmlb$1ktm5$6@dont-email.me>
 <vstl33$p9c2$1@dont-email.me> <vstme2$n9gi$2@dont-email.me>
 <HMScneI80ehcN2_6nZ2dnZfqn_SdnZ2d@brightview.co.uk>
 <vsuc78$1f8in$1@dont-email.me>
 <356fe829b105738f556ce1f89999ae620dcd2071@i2pn2.org>
 <87y0waqknw.fsf@nosuchdomain.example.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 9 Apr 2025 01:31:43 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3734754"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
Content-Language: en-US
In-Reply-To: <87y0waqknw.fsf@nosuchdomain.example.com>
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 6074
Lines: 91

On 4/8/25 7:48 PM, Keith Thompson wrote:
> Richard Damon <richard@damon-family.org> writes:
> [...]
>> And from what I see, the issue is that while each of the numbers in
>> the list could be defined as constructable, in that a algorithm exists
>> that given n, it will give at least n digits of that number, there
>> doesn't need to be a master algorithm, that given k and n gives the
>> first n digits of the kth number, that can be shown to cover the full
>> set of constructable numbers (but perhaps an countable infinite subset
>> of them). Without that master algorithm, the method of constructing
>> the diagonal isn't actually an implementable algorithm.
>>
>> We can't just iterate through all possible machines, because not all
>> machines are halting, let alone meet the requirements for the
>> construction machines.
>>
>> Thus, we don't have an actual algorithm that makes the diagonal number
>> constructable.
> 
> So it's the Halting Problem that makes it impossible to computationally
> generate a list of all computable numbers, even though there are only a
> countable infinity of them.

It is at least related, and there are a number of theories that all tie 
together here, really hinging on the fact that the countable infinite 
concept spans the gap between finiteness and infiniteness.


> 
> Cantor's proof applies correctly to the real numbers.  Given a purported
> infinite list of all the real numbers, we can construct a real number
> that's not in the list; therefore there is no such list.
> 
> The same proof does not apply to rational numbers.  We can generate an
> infinite list of all the rational numbers, and the diagonal construction
> demonstrates the existence of a number that's not on the list, but any
> such number is not rational, so there's no contradiction.  Same thing
> for algebraic numbers.  The rational and algebraic numbers *can* be
> placed into a one-to-one mapping with the integers.
> 
> There are only a countable infinity of computable numbers (right?),
> but if I understand correctly the halting problem prevents us
> from generating a list of them.  Given a purported list of all the
> computable numbers, diagonalization gives us a computable number
> that's not in the list.

Since there are only a countable number of machines that could compute 
numbers, there must be no more than a countable infinity of such numbers.

The diagonalization doesn't give us a computable number, as the 
diagonalization uses an operation that isn't "computable", namely select 
the algorithm for the nth number on the list. (or at least that 
operation isn't computable if there are an infinite number of numbers on 
the list).

It does show that there can't be a finite number of computable numbers, 
but there are simpler ways to prove that.

> 
> There is no list of real numbers because there are strictly more real
> numbers than integers.

THAT isn't a true statement. I resently saw a demonstration of how with 
the Axiom of Choice, we can create an uncountably long list of the Real 
Numbers, All the non-rational numbers get pairs to ordinal like 5 omega 
+ 12, but the list can be made. It just isn't countable.

> 
> There is no list of computable numbers, but for a different reason.
> There are *not* strictly more computable numbers than integers,
> but the halting problem makes it impossible to construct a list
> of them.  (Generate an ordered list of all possible algorithms in
> some notation.  Eliminate the ones that don't generate a computable
> number.  But we can't perform the elimination step because it would
> require solving the halting problem.)

Again, I don't think that holds. an ordered list of the computable 
numbers exists (in fact an infinite number of them), we just may not be 
able to compute that list. Strangely, we

> 
> It feels intuitively weird that there is a set of numbers that is
> countably infinite but we can't generate an ordered list of them.
> But sometimes math is like that.
> 
> I suspect I'm still missing something.  For one thing, I'm not
> sure whether "we can't computationally generate the list" and "the
> list doesn't exist" are equivalent statements.
> 

They aren't, at least not if you accept the axiom of choice, which is 
part of the normal basis for the counting numbers.