Why are reals uncountable yet algorithms countable (long)?

From: Ray Whitmer (ray_at_xmission.com)
Date: 11/14/04 

Date: Sun, 14 Nov 2004 10:49:42 -0700

Go easy on me. I am no mathematician :-), nor do I follow this group as
much as I would like to, so I am sure this sort of thing is discussed here
often enough. I am trying to understand this better. Give me a pointer
to a FAQ if it answers the question.

I have always had a bit of trouble with what is, I believe, the
diagonal(ization)? proof that shows that the reals are uncountable (by
Cantor I believe?). To me, it seems rooted in infinity-based paradoxes,
the likes of which could also be used to prove many more alternative
conclusions.

If you are going to say: construct a number from one digit
unequal to each digit of a member of the set, how do you know that this is
possible at all? It seems to lie way outside the normal experience, since
you cannot enumerate the infinite digits.I have read that, unlike reals,
algorithms are supposed to be countable (since Turing machines can be
enumerated).

A countable subset of all algorithms would seem to be algorithms producing
the bit sequence of any real number as output (both finite and infinite).
Any real number you can identify (without self-contradiction), I can tell
you the algorithm number that produces it, which makes it
countable.

Presumably, one of these algorithms would also be an algorithm
that produces a number different from the first digit of the output of the
first algorithm in the first digit, different from the second digit of the
output of the second algorithm in the second digit, different from the
third digit of the output of the third algorithm in the third digit, etc.
I assure you that if you can enumerate algorithms, I can write that
additional algorithm.

But eventually you reach the algorithm itself that is generating the
difference bits, that by definition should produce some bit but never the
bit it actually produces since it is defined to contradict itself.To me,
this seems like a simple result of something like incompleteness theorum,
arising from a definition that inherently contradict itself.

Does this really mean that the reals are uncountable -- that my
enumeration of algorithms cannot produce all reals? Perhaps it is unfair
to ask for a counterexample -- a real that it cannot produce. But to me
it seems philosophical, rather than useful to assume the existence of
reals which cannot be algorithmically produced, because the definition
seems to be a dog-ate-my-homework, or angels on the head of a pin type of
answer that the counterexamples exist, but cannot, by definition, be
observed.

I suspect I could produce similar examples, for example, even in rational
space, if I assume the existence of undetectable rationals, that are
self-contradictory by definition, and show that they cannot be counted in
the enumeration of rationals.

The production of numbers, whether real or rational, which are
self-contradictory and therefore undetectable by us seems not particularly
useful at best.

I believe the same proof could be used to show that algorithms are
uncountable, because I just talked about the algorithm that is missing
from every enumeration: the algorithm that uses each of the other
real-generating algorithms in-turn to generate bits that differ from them.

How about integers:

I could assert that I have an integer that differs from the first digit of
1 in the first digit, differs from the second digit of 2 in the second
digit, differs from the third digit of 3 in the third digit, differs from
4th digit of 4 in the 4th digit, ... and therefore never occurs at all in
the enumeration of integers. Sure, there are contradictions here, but are
they any greater than other contradictions we have examined?

What does uncountability of reals really mean? Anything useful? How can
I get a better understanding about these supposed uncounted reals?

Thanks,

Ray Whitmer
ray@xmission.com

Relevant Pages

  • Re: Why are reals uncountable yet algorithms countable (long)?
    ... proof that shows that the reals are uncountable (by ... > If you are going to say: construct a number from one digit ... one of these algorithms would also be an algorithm ... > enumeration of algorithms cannot produce all reals? ...
    (sci.math)
  • Re: No Set Contains Every Computable Natural (was Church-Turing compared to Zuse-Fredkin thesis)
    ... Russell is right about Turing saying this, ... You might not want to call this an algorithm which has ... decimal representation of x digit by digit. ...
    (comp.theory)
  • Re: Powers and logic
    ... quasi wrote: ... It is easy to give an algorithm which could be calculated ... one can always find the leading digit by inspection. ... The space requirement would exceed the capacity of ...
    (sci.math)
  • Re: Large-numbers division way too slow -- what to do?
    ... > algorithm is now responsible for most of the slowness. ... I want to return the quotient or the remainder). ... In the division function, at the very bottom, I placed: ... processing the last digit becomes the remainder. ...
    (sci.crypt)
  • Re: continued fractions
    ... The "one bit at a time" algorithm is just a special case of the ... The dividend and divisor will be expressed as ... The crucial part here is the "guessing" of the digit. ... digit is 1, and the result of the subtraction is your new w; ...
    (comp.lang.forth)
Loading