Re: Why are reals uncountable yet algorithms countable (long)?
From: KRamsay (kramsay_at_aol.com)
Date: 11/19/04
- Next message: KRamsay: "Re: Why are reals uncountable yet algorithms countable (long)?"
- Previous message: KRamsay: "Re: Why are reals uncountable yet algorithms countable (long)?"
- In reply to: Shmuel (Seymour J.) Metz: "Re: Why are reals uncountable yet algorithms countable (long)?"
- Next in thread: J.E.: "Re: Why are reals uncountable yet algorithms countable (long)?"
- Reply: J.E.: "Re: Why are reals uncountable yet algorithms countable (long)?"
- Messages sorted by: [ date ] [ thread ]
Date: 19 Nov 2004 04:51:11 GMT
In article <419bfbac$13$fuzhry+tra$mr2ice@news.patriot.net>, "Shmuel (Seymour
J.) Metz" <spamtrap@library.lspace.org.invalid> writes:
|I know of no Mathematician who defines the reals in terms of decimal
|expansions.
Neither do I, and it seems to be with good reason. I remember once
a mathematician wondering aloud about the possibility of defining them
that way, perhaps in an introductory real analysis textbook, thinking
that students might find it agreeable.
After thinking aloud for awhile he changed his mind; the technical details
seem to become that much more unpleasant. One of the main problems
is with "carrying". Given two decimal expansions, such as 2.71828...
and 3.14159..., we trivially get sequences of rationals converging to the
numbers they represent, 2, 27/10, 271/100, ... and 3, 31/10, 314/100,....
It does then follow that the sequence of products, 2*3, (27/10)(31/10),...
converges to the product of the two numbers. But if one is thinking in
terms of decimal expansions, things are messy, because in order to
determine what the decimal expansion of the product is, one might have
to look arbitrarily far ahead in the expansions to see whether there is
a carry into the n-th decimal place of the number.
It's easier to just get the students used to the idea that a decimal
expansion is just a special case of a converging sequence of rationals.
It's usual, in fact, to define "computable" real number in terms of
the computability of a sequence of rationals converging to the number
rather than the computability of the decimal expansion of the number.
Those are equivalent, but the former definition is better behaved.
If you give me two programs, one which when given as input a number
n computes an approximation to within 1/n of a real number a, and a
second such program for a real number b, then I can give you a
program that computes an approximation to within 1/n of a+b when
given n. All it has to do is use the two subprograms to compute
rational approximations to within 1/2n of a and b respectively and
add them together.
On the other hand, if you give me two programs that compute the
decimal expansions of a and b (in the sense of being able to give
the n-th digit for any given n), I will not necessarily be able to give
you a program that computes the decimals of a+b. To compute the
n-th digit, it's not good enough to compute the first n digits of a
and b separately, since there may be a carry from later digits. And
there is no upper limit on how many additional digits there might
be before we get the carry. In principle there's an algorithm that
computes the decimal digits of a+b, because if a+b is a terminating
decimal expansion, then there is a program that just keeps the
expansion stored away, and if a+b is not expressible as a terminating
decimal expansion, every time when we need to know whether there
is a carry-over from a later digit, we can determine whether there is
by computing enough more digits of a and b. But that's nonconstructive
since we have no way of necessarily knowing whether a+b has a
terminating decimal expansion or not.
Keith Ramsay
- Next message: KRamsay: "Re: Why are reals uncountable yet algorithms countable (long)?"
- Previous message: KRamsay: "Re: Why are reals uncountable yet algorithms countable (long)?"
- In reply to: Shmuel (Seymour J.) Metz: "Re: Why are reals uncountable yet algorithms countable (long)?"
- Next in thread: J.E.: "Re: Why are reals uncountable yet algorithms countable (long)?"
- Reply: J.E.: "Re: Why are reals uncountable yet algorithms countable (long)?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
