Re: Why are reals uncountable yet algorithms countable (long)?

From: robert j. kolker (nowhere_at_nowhere.net)
Date: 11/15/04 

Date: Mon, 15 Nov 2004 11:53:51 -0500

Ray Whitmer wrote:
>
> Now we are getting to the heart of ny question. What is the nature of
> these uncomputable reals, and how are they useful. Is the set of
> uncomputable reals a well-known notion that I can read about in a math
> book or math paper. How do we know they exist if we cannot identify an
> instance of them?

The so-called computable reals are those sequences which can be
generated by a Turing machine. Since there are only a countable set of
Turing machines there can only be a countable set of computable reals.
HOWEVER the set of decimal fraction expansions we know are uncountable
(because the assumption of countability leads to a contradiction -- the
well know diagnonal proof) so we know there exist decimal expansions not
generatble by any Turning machine. Clearly we cannot exhibit one,
otherwise it would be generatble. So we are in the embarrasing position
of proving something exists, but not able to exhibit, construct it or
generate it.

There is a school of mathematical thought that would require all kosher
mathematical entitiies to be constructable according to a finite
algorithm but such a diminished system of mathematics cannot prove some
really cool useful stuff.

However, here is the good news. The set of computable reals is -dense-
in the set of all reals, so that any uncomputable real can be
approximated to any degree of accuracy by a computable real.

>
> I believe a Turing machine can produce any sequence of digits that can be
> described (counter-examples, please). Where are the uncomputable numbers
> hiding?

They are not hiding anywhere. They are just out of reach. We know they
exist but we cannot exhibit or construct them.

That is the penalty we pay for being finite beings with limited time of
existence in the universe.

Bob Kolker

Relevant Pages

  • Re: Problem demonstrating that the set of binary strings is uncountable.
    ... you have to admit the possibility of uncomputable reals. ... > of uncomputable reals without the diagonal method. ... > computable reals and a finite number of uncomputable reals, ...
    (sci.math)
  • Re: Why are reals uncountable yet algorithms countable (long)?
    ... > the reals implies that there exist uncomputable reals, ... these uncomputable reals, ... I believe a Turing machine can produce any sequence of digits that can be ... generating occurs at some finite enumeration index within that list. ...
    (sci.math)
  • Re: Why are reals uncountable yet algorithms countable (long)?
    ... >> the reals implies that there exist uncomputable reals, ... > generating occurs at some finite enumeration index within that list. ... > Assuming anything else assumes the very contradiction that was supposedly ...
    (sci.math)
  • Re: Mueckenherz Confusion
    ... to label", ditto. ... rather that to make the calculus work, we need the whole set of reals, ... as a set, which includes uncomputable reals. ...
    (sci.math)
  • Re: Mueckenherz Confusion
    ... the point would be that the "computable" reals represent 0% of the ... isn't their existence just an ... tries to use mathematics a big headache. ... My current train of thought was that the existence of infinite sets and uncomputable reals seems to be a matter of choice - analogous to the use of the sqrt of -1 to extend real to complex analysis? ...
    (sci.math)
Quantcast