At 10:48 PM 1/18/1997, Secret Squirrel wrote:
Is it REALLY true that there are real numbers that cannot be generated by any algorithm? Some guy said that since the set of algorithms is countable, but the set of real numbers is more than countable, there must be some numbers for which there is no algorithms that generate them.
There are sets of real numbers whose existence we can prove, but which we cannot otherwise describe. This is more extreme than being "generated by an algorithm". We can't even tell somebody which numbers to generate! (I take "to generate" here to mean "to compute a decimal approximation.") The set of real numbers is uncountable as is the set of subsets of the real numbers. Yet, we have only countably infinite ways to describe sets of numbers. All sets of numbers which we can describe can be described with a finite set of symbols. (Human beings are unable to distinguish between an infinite number of states.) The set of combinations of this finite set is infinite, but countable. "What we cannot speak about we must pass over in silence." - Ludwig Wittgenstein, closing line of "Tractatus Logico-Philosophicus" See the early pages of "Godel's Incompleteness Theorems" by Raymond M. Smullyan for a better exposition. Math Man